本文主要是介绍51nod 1163 最高的奖励 贪心，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
有N个任务，每个任务有一个最晚结束时间以及一个对应的奖励。在结束时间之前完成该任务，就可以获得对应的奖励。完成每一个任务所需的时间都是1个单位时间。有时候完成所有任务是不可能的，因为时间上可能会有冲突，这需要你来取舍。求能够获得的最高奖励。
Input
第1行：一个数N，表示任务的数量(2 <= N <= 50000) 第2 - N + 1行，每行2个数，中间用空格分隔，表示任务的最晚结束时间E[i]以及对应的奖励W[i]。(1 <= E[i] <= 10^9，1 <= W[i] <= 10^9)
Output
输出能够获得的最高奖励。
Input示例
7 4 20 2 60 4 70 3 40 1 30 4 50 6 10
Output示例
230
题解：
贪心，先对时间进行从小到大排序
然后从头开始贪心选择，放入优先队列中，由于默认是大根堆的优先队列，所以放入的时候放相反数，最小价值的相反数在根
若是前面的数的个数已经大于结束时间了（因为每个任务都消耗一个时间），所以去掉价值最小的任务就可以了
#include<queue>
#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;pair<int,int>a[50010];
priority_queue<int>q;///默认是大根堆
long long n,ans;int main()
{//freopen("in.txt","r",stdin);while(scanf("%lld",&n)!=EOF){for(int i=0;i<n;i++)scanf("%d%d",&a[i].first,&a[i].second);sort(a,a+n);/*按照第一个从小打到排序，第一个值相同的时候第二个升序for(int i=0;i<n;i++)printf("%d %d\n",a[i].first,a[i].second);*/for(int i=0;i<n;i++){q.push(-a[i].second);///转化为小根堆ans+=a[i].second;if(q.size() > a[i].first){///如果前面所有时间排满了ans+=q.top();q.pop();///就不要价值小的}}printf("%lld\n",ans);}return 0;
}
这篇关于51nod 1163 最高的奖励 贪心的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
