首页 > 代码库 > NYOJ 1107 最高的奖励 【贪心】+【路径压缩】
NYOJ 1107 最高的奖励 【贪心】+【路径压缩】
最高的奖励
时间限制:1000 ms | 内存限制:65535 KB
难度:3
- 描述
请问:挖掘机技术哪家强?AC了告诉你!
给你N(N<=3*10^4)个任务,每个任务有一个截止完成时间t(1=<t<=10^9)和完成该任务的奖励v(1=<v<=10^9),每个任务要花一天完成,问最多能获得多少奖励?
- 输入
- 多组 测试数据。
第一行一个数N,表示任务总数。
接下来N行,每行两个数t和v,如上所述。 - 输出
- 对于每组数据输出最高的奖励。
- 样例输入
7 4 20 2 60 4 70 3 40 1 30 4 50 6 10
- 样例输出
230
代码:
#include <cstdio> #include <cstring> #include <algorithm> using namespace std; #define M 30500 struct node{ int t, v; }s[M]; int fat[M]; bool cmp(node a, node b){ return a.v > b.v; } int f(int x){ if(fat[x] <= 0) return -1; else if(fat[x] == x) return fat[x] = x-1; else fat[x] = f(fat[x]); } int main(){ int n; while(scanf("%d", &n) == 1){ int i; for(i = 0; i < n; i ++){ scanf("%d%d", &s[i].t, &s[i].v); fat[i] = i; if(s[i].t > n) s[i].t = n; } fat[n] = n; sort(s, s+n, cmp); long long sum = 0; for(i = 0; i < n; i ++){ if(f(s[i].t) >= 0){ sum += s[i].v; } } printf("%lld\n", sum); } return 0; }
NYOJ 1107 最高的奖励 【贪心】+【路径压缩】
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。