【51Nod - 1163】最高的奖励 （贪心+优先队列 或 妙用并查集）

题干：

有N个任务，每个任务有一个最晚结束时间以及一个对应的奖励。在结束时间之前完成该任务，就可以获得对应的奖励。完成每一个任务所需的时间都是1个单位时间。有时候完成所有任务是不可能的，因为时间上可能会有冲突，这需要你来取舍。求能够获得的最高奖励。

Input

第1行：一个数N，表示任务的数量(2 <= N <= 50000) 
第2 - N + 1行，每行2个数，中间用空格分隔，表示任务的最晚结束时间Eii以及对应的奖励Wii。(1 <= Eii <= 10^9，1 <= Wii <= 10^9)

Output

输出能够获得的最高奖励。

Sample Input

7
4 20
2 60
4 70
3 40
1 30
4 50
6 10

Sample Output

230

解题报告：

    烂大街的优先队列贪心就不再赘述了、、、这题偶然发现可以并查集你敢信，，，首先按照权值排序，然后遍历找到可以最早进行该任务的时间，用并查集来合并这个时间并且找到可以执行这个时间的最晚时间（也就是在这一步贪心了），因为对于这个任务，肯定越晚完成越好，因为可以留更多的时间给其他的任务。然后如果实在找不到时间了那就GG了，这个任务不能选了。因为有其他更优秀的任务占据了这个时间，整个过程用并查集维护。

AC代码：

#include<bits/stdc++.h>
#define ll long long
#define fi first
#define se second
using namespace std;
const int MAX = 50000 + 5;
ll f[MAX];
pair <ll,ll> p[MAX];
 
int find(int x){
	if(x<=0) return -1; 
	if(x==f[x]) return f[x]=x-1; 
	else return f[x] = find(f[x]); 
} 

int main()
{
	ll n,sum=0;
	cin>>n;
	for(int i = 1; i<=n; i++){
		f[i]=i;
		scanf("%d%d",&p[i].se,&p[i].fi);
		p[i].fi=-p[i].fi;
	}
	sort(p+1,p+n+1);
	for(int i = 1; i<=n; i++){
		if(find(p[i].se)>=0) sum += (-p[i].fi);
	}
	printf("%lldn",sum);
	return 0;
}

优先队列AC代码：

//按起点排序，优先队列维护
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
using namespace std;
struct Node {
	int t,w;
} node[50000 + 18];
bool cmp(const Node & a,const Node & b) {
	if(a.t!=b.t) return a.t<b.t;
	else return a.w<b.w;
} 

priority_queue <int,vector<int>,greater<int> > pq;
int main()
{
	int n;
	int maxtime,cur=0;
	long long ans=0;
	cin>>n;
	for(int i = 0; i<n; i++) {
		scanf("%d %d",&node[i].t,&node[i].w);
		maxtime=max(maxtime,node[i].t); 
	}
	sort(node,node+n,cmp);
	for(int i = 0;i<n; i++)
		if(cur < node[i].t) {
			pq.push(node[i].w);
			cur++;
		}
		else if(cur == node[i].t) {
			if(node[i].w > pq.top() ) {
				pq.pop();
				pq.push(node[i].w);
			}
		}
	while(!pq.empty() ) {
		ans+=pq.top();
		pq.pop();
	}
	printf("%lldn",ans);
	return 0 ;
}

最后

以上就是哭泣电话为你收集整理的【51Nod - 1163】最高的奖励 （贪心+优先队列 或 妙用并查集）的全部内容，希望文章能够帮你解决【51Nod - 1163】最高的奖励 （贪心+优先队列 或 妙用并查集）所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。