51 nod 最高奖励（贪心+优先队列）

题目：https://cn.vjudge.net/contest/178387#problem/H

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

思路：这道题和HDU1789是一样的，都是给你任务的时间和及价值，让你求最大价值。但是这道题如果用直接按照价值排序，然后在最晚截止日期内做价值从大到小的是会超时的，因为这里数据规模T为1e9，再加上一层循环就爆了。

所以要进行优化。利用优先队列的方式对该问题进行模拟。在队列里按照价值从小到大，先将所有任务按照时间从早到晚。队列里的size（）表示进行的活动数量，即活动进行到的天数，如果新的活动的时间a[i].d<size,表示新的活动和之前的活动冲突，要选择价值大的留下，所以把价值最小的去掉，加入价值大的；否则直接加入队列。

有关于优先队列的用法可以看http://www.cnblogs.com/void/archive/2012/02/01/2335224.html

#include<iostream>
#include<algorithm>
#include<stdio.h>
#include<string.h>
#include<queue>
using namespace std;
#define maxn 50000+5
struct node {
	int day, value;
	friend bool operator<(node x,node y)
	{
		return x.value > y.value;//表示队列按照价值从小到大
	}
}a[maxn];
bool cmp(node x, node y)
{
		return x.day < y.day;//按照时间排序
}
int main()
{
	int n, i, j,maxday=0;
	
	while (~scanf("%d", &n))
	{
		priority_queue<node>pq;
		long long ans = 0; 
		for (i = 1; i <= n; i++)
		{
			scanf("%d%d", &a[i].day, &a[i].value);
		}
		sort(a + 1, a + n + 1, cmp);
		for (i = 1; i <= n; i++)
		{
			if (a[i].day > pq.size())
			{
				pq.push(a[i]);
				ans += a[i].value;
			}
			else
			{
				pq.push(a[i]);
				ans += a[i].value;
				ans -= pq.top().value;//最小的价值的任务去掉
				pq.pop();			
			}
		}
		cout << ans << endl;
	}
	return 0;
}

最后

以上就是想人陪橘子为你收集整理的51 nod 最高奖励（贪心+优先队列）的全部内容，希望文章能够帮你解决51 nod 最高奖励（贪心+优先队列）所遇到的程序开发问题。

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