专栏首页落影的专栏程序员进阶之算法练习(四十六)

程序员进阶之算法练习(四十六)

正文

题目1. Ichihime and Triangle

题目链接 题目大意: 输入4个整数? , ?, ?, ?, 并且 ?≤?≤?≤?; 现在需要找三个整数?, ?, ?,满足: ?≤?≤?. ?≤?≤?. ?≤?≤?. 并且?, ?, ?能构成一个三角形。

输入: 第一行,整数?表示有t个样例数量 (1≤?≤1000) 接下来每个样例一行,四个整数? , ?, ?, ? (1≤?≤?≤?≤?≤10^9)

输出: 每个样例一行,三个s整数?, ?, ?;

Examples input 4 1 3 5 7 1 5 5 7 100000 200000 300000 400000 1 1 977539810 977539810

output 3 4 5 5 5 5 182690 214748 300999 1 977539810 977539810

样例解释 3 4 5

样例解释5 5 5

题目解析: 三角形要满足两边之和大于第三边,由题目意思我们知道x≤y≤z; 所以只要满足,x+y≥z即可; 所以令y=z,那么x随便取值即可。

    int t;
    cin >> t;
    while (t--) {
        int a[4];
        for (int i = 0; i < 4; ++i) {
            cin >> a[i];
        }
        cout << a[1] << " " << a[2] << " " << a[2] << endl;
    }   

题目2. Kana and Dragon Quest game

题目链接 题目大意: 小明在打游戏,遇到了一条恶龙; 恶龙血量为x,小明可以释放两个技能: 技能1:使龙的血量变为x/2+10,x/2为向下取整; 技能2:使龙的血量减10; 当龙的血量小于等于零时,小明会赢得胜利;

小明最多可以释放n个技能1和m个技能2,现在想知道,小明是否能否打败恶龙;

输入: 第一行,整数?表示有t个样例数量 (1≤?≤1000) 接下来每个样例一行,整数? , ?, ? (1≤?≤10^5, 0≤?,?≤30)

输出: 每个样例一行,如果小明可以打败恶龙,输出YES;如果无法打败,则输出NO;

Examples input 7 100 3 4 189 3 4 64 2 3 63 2 3 30 27 7 10 9 1 69117 21 2 output YES NO NO YES YES YES YES

题目解析: 题目只考虑是否能打败,而不是最优解,可以直接将技能1释放完,只要技能1不会使恶龙血量增加; 然后再全部放完技能2,看最终血量是否小于等于0即可;

思考?: 贪心!

    int t;
    cin >> t;
    while (t--) {
        int x, n, m;
        cin >>x >> n >> m;
        while (n && (x / 2 + 10 < x)) {
            --n;
            x = x / 2  +10;
        }
        if (x <= m * 10) {
            cout << "YES" << endl;
        }
        else {
            cout << "NO" << endl;
        }
    }   

题目3. Linova and Kingdom

题目链接 题目大意: 有n个城市,用n-1条道路相连,并且保证任意两个城市之间都可以通过道路相连; 作为女王,小明需要选出k个城市作为工业城市,剩下的n-k个城市作为旅游城市。 城市1是首都,现在要召开工业会议,每个工业城市都会派出一个使者到城市1参加会议,使者会沿着道路按照最短的路径直接到达城市1,使者的快乐值等于沿途经过的旅游城市的数量。

小明想知道,如何选择工业城市,使得所有使者的快乐值总和最大? (城市1可以是工业城市,也可以旅游城市) 输入: 第一行,整数 ? and ? (2≤?≤2⋅105, 1≤?<?) 接下来n-1行,每行两个整数 ? and ? ,表示城市u和城市v之间有一条道路 (1≤?,?≤?)

输出: 一个整数,表示所有使者的快乐值总和的最大值;

Examples input 7 4 1 2 1 3 1 4 3 5 3 6 4 7 output 7

样例解释

input 4 1 1 2 1 3 2 4 output 2

样例解释

题目解析: 一开始是用贪心的思路:先dfs遍历,记录每个点的深度和子节点的数量; 按照深度,从大到小排序,再按子节点的大小,从小到大排序; 然后,从深度最大的开始,填充节点;相同深度,优先填充子节点少的; 最后再遍历一遍,得到结果。 复杂度NlogN。

提交之后,喜提一个Wrong Answer。

重新思考:正确的做法是评估,每一个点的价值和代价,上面只考虑了价值,忽略了代价的问题。

vector<int> g[N];
int vis[N];

void dfsCount(int u, int dep) {
    node[u].first = dep;
    node[u].val = u;
    vis[u] = 1;
    for (int i = 0; i < g[u].size(); ++i) {
        int v = g[u][i];
        if (!vis[v]) {
            dfsCount(v, dep + 1);
            node[u].second += node[v].second + 1;
        }
    }
    node[u].cost = dep - node[u].second;
}

int main(int argc, const char * argv[]) {
    // insert code here...
    
    int n, k;
    cin >> n >> k;
    for (int i = 1; i < n; ++i) {
        int u, v;
        cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    dfsCount(1, 0);
    sort(node + 1, node + n + 1);
    
    lld sum = 0;
    for (int i = 1; i <= k; ++i) {
        sum = sum + node[i].cost;
    }
    cout << sum << endl;
    
    return 0;
}

题目4. Fedor and coupons

题目链接 题目大意: 小明去商场购物,有若干个商品排成一行。 小明有n张优惠券,每张优惠券可以覆盖id范围是(l[i], r[i])的商品,包括第l[i]、r[i]个商品; 现在小明想从中选出k张优惠券,并且让这k张优惠券共同覆盖的商品尽可能多; 输出最多的商品数,还有选中的k张购物券。

输入数据 第一行两个整数,n and k (1 ≤ k ≤ n ≤ 3·1e5) 接下来n行,每行两个整数 l[i] and r[i] ( - 1e9 ≤ l[i] ≤ r[i] ≤ 1e9)

输出数据 第一行是最多覆盖的商品数; 第二行是k个整数,表示选中的k张购物券;

Examples input 4 2 1 100 40 70 120 130 125 180 output 31 1 2 样例解释: 共同覆盖的区间是[40, 70],总共有31种商品; input 3 2 1 12 15 20 25 30 output 0 1 2 样例解释:没有共同覆盖的区间,任选两张即可。

题目解析: 容易知道优惠券的选择是没有先后顺序,可以对其进行排序。 先保证左区间从小到大,再考虑右区间从小到大。

对于购物券i覆盖的区间(l[i], r[i]),如果之前某个购物券(我们用j来表示),其覆盖区间的r[j] < l[i]; (j < i) 那么就有l[i] > r[j] >= l[j]; 即是购物券i的覆盖区间是在购物券j覆盖区间的右边; 并且对于购物券i+1覆盖区间,因为有l[i+1] >= l[i], 那么购物券 i+1的覆盖区间必然也是在购物券j的覆盖区间右边;

由此,我们可以维护一个优先队列:里面有若干个值,r最小的在前面,如果r相同则让大的在前面; 由于前面我们已经按照左区间从小到大排序,那么对于第i张优惠券,l[i]就是最大的left,再拿优先队列里面的top.r,就是最小右区间; l[i]和top.r形成的区间,就是优先队列里面的所有区间的公共覆盖区间,再判断下优先队列里面的区间是否大于k。

注意题目还要求输出k个优惠券,如果求解过程去记住这个值,很容易超时; 可以只记录最长的公共覆盖区间ans,输出答案的时候通过遍历所有优惠券,如果该优惠券的覆盖区间超过输出ans,则直接输出。

#include<cstdio>
#include<cmath>
#include<stack>
#include<map>
#include<set>
#include<queue>
#include<deque>
#include<string>
#include<utility>
#include<sstream>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;

typedef long long lld;
const int N = 301000, M = 3010100, inf = 0x7fffffff;
const lld llinf = 0x7fffffff7fffffffll;

struct Node {
    int l, r, id;
    bool operator < (const Node &tmp) const
    {
        if (r != tmp.r) return r > tmp.r; // 优先队列默认是大顶堆,但是我们希望r小的在前面
        else return l < tmp.l; // 如果r相同,那么希望l大的在前面
    };
    Node(int first, int second, int id):l(first), r(second), id(id){};
    Node(){};
}a[N];

bool cmp(Node x, Node y) {
    if (x.l != y.l) {
        return x.l < y.l;
    }
    else {
        return x.r < y.r;
    }
}

int main(int argc, const char * argv[]) {
    // insert code here...
    int k, n;
    cin >> n >> k;
    for (int i = 0; i < n; ++i) {
        scanf("%d%d", &a[i].l, &a[i].r);
        a[i].id = i + 1;
    }
    sort(a, a + n, cmp);
    priority_queue<Node> priQueue;
    int ans = 0;
    pair<int, int> seg;
    for (int i = 0; i < n; ++i) {
        // 优先队列里面有若干个值,r最小的在前面,假设是top.r,l最大的是l[i],那么这些区间的公共区域是 l[i] 到 r
        while (!priQueue.empty()) {
            Node top = priQueue.top();
            if (top.r < a[i].l) {
                priQueue.pop();
                continue;
            }
            else {
                break;
            }
        }
        while (priQueue.size() >= k) {
            priQueue.pop();
        }
        
        if (priQueue.size() == k - 1) {
            int topR;
            if (priQueue.size() == 0) {
                topR = a[i].r;
            }
            else {
                topR = min(priQueue.top().r, a[i].r);
            }
            if (ans < topR - a[i].l + 1) {
                ans = topR - a[i].l + 1;
                seg = make_pair(a[i].l, topR);
            }
        }
        priQueue.push(a[i]);
    }
    
    if (ans == 0) {
        cout << 0 << endl;
        for (int i = 0; i < k; ++i) {
            printf("%d ", i + 1);
        }
    }
    else {
        cout << ans << endl;
        for (int i = 0; i < n && k; ++i) {
            if (a[i].l <= seg.first && a[i].r >= seg.second) {
                printf("%d ", a[i].id);
                --k;
            }
        }
        cout << endl;
    }
    
    return 0;
}

总结

题目1是简单思维,三角形的基本性质; 题目2是典型的贪心题目,代码非常简单; 题目3是贪心类似的思路,可以用代价和价值来简化思考; 题目4要先对数据做预处理,是典型的区间覆盖问题。

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 程序员进阶之算法练习(十六)

    前言 正文6道题目来自leetcode––为求职为生的编程网站,目的是工作闲暇之时锤炼代码功底。 没有捷径,但手熟尔; 一步领先,步步领先。 正文 5. L...

    落影
  • 程序员进阶之算法练习(四十四)

    题目链接 题目大意: 给出整数x,求两个整数a和b,满足: ???(?,?)+???(?,?)=? . GCD是最大公约数; LCM是最小公约数;

    落影
  • 程序员进阶之算法练习(十四)

    前言 坚持做算法练习对开发的好处是抽象能力变强,拿到一个需求能很快对其进行抽象,然后再用学过的设计模式相关知识进行整理,最后用代码实现。 最大的好处在于:对...

    落影
  • 程序员进阶之算法练习(二十六)

    前言 金三银四,求职黄金月做算法面试题,热热身子。 正文 1.Chess For Three 题目链接 题目大意: 有三个人A,B,C玩剪刀石头布的游戏,但...

    落影
  • 程序员进阶之算法练习(二十四)

    前言 已经有三个月未更新算法文章,大厂工作环境是步步紧逼的,使得所有的人越来越忙碌。余下的学习时间,要用于技术预研、知识面开阔、底层原理理解等等,慢慢算法只能占...

    落影
  • 程序员进阶之算法练习(四十二)

    题目链接 题目大意: n个学生参加测试,一共有m道题,每道题的答案可能是(A, B, C, D , E)中的一个; m道题分别有?1,?2,…,??,共m...

    落影
  • 程序员进阶之算法练习(四十七)

    题目链接 题目大意: 给出一个整数1~n的排列。 接下来有m个询问,每个询问包括 l, r, x。 (l <= x <= r) [l, r]区间内的数字...

    落影
  • 程序员进阶之算法练习(四十五)

    每个路口的机动车道有三个方向,分别是左转、直行、右转,同时路口有一条人行道; 每行输入有四个数字l,s,r,p,分别表示左转、直行、右转、人行道的交通信号灯是...

    落影
  • 程序员进阶之算法练习(四十一)

    题目链接 题目大意: 有一个由数字0、1组成的字符串,长度为n; 现在需要将其切分成若干段,要求每一段0和1的数量是不相同的。 比如说1, 101, 0...

    落影

扫码关注云+社区

领取腾讯云代金券