首页 > 代码库 > 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 最高的奖励 【贪心】+【路径压缩】