51nod 1163 最高的奖励 (贪心贪心+优先队列)

xiaoxiao2021-02-28  9

有N个任务,每个任务有一个最晚结束时间以及一个对应的奖励。在结束时间之前完成该任务,就可以获得对应的奖励。完成每一个任务所需的时间都是1个单位时间。有时候完成所有任务是不可能的,因为时间上可能会有冲突,这需要你来取舍。求能够获得的最高奖励。 Input 第1行:一个数N,表示任务的数量(2 <= N <= 50000)  第2 - N + 1行,每行2个数,中间用空格分隔,表示任务的最晚结束时间E i i以及对应的奖励W i i。(1 <= E i i <= 10^9,1 <= W i i <= 10^9) Output 输出能够获得的最高奖励。 Sample Input 7 4 20 2 60 4 70 3 40 1 30 4 50 6 10 Sample Output 230 思路:先对分数进行排序,之后把所有的奖励全加在一起,之后模拟一遍,如果要求的天数还没达到最晚时间就往后排,实在是后面排不下了就总奖励减去这个奖励。 代码如下: #include<iostream> #include<cstdio> #include<cstring> #include<algorithm> using namespace std; struct node { long long x,y; }; bool cmp(node n,node m) { if(n.y!=m.y) return n.y>m.y; else return n.x<m.x; } int main() { int n,m,i,j; struct node std[50010]; int a[50010]; scanf("%d",&n); long long sum=0; memset(a,0,sizeof(a)); for(i=0; i<n; i++) { scanf("%lld %lld",&std[i].x,&std[i].y); sum+=std[i].y; } sort(std,std+n,cmp); for(i=0; i<n; i++) { for(j=std[i].x; j>0; j--)//往尽可能的往后排 { if(a[j]==0) { a[j]=1; break; } } if(j<=0)//后面的天数都已经排好了,又因为前面已经对分数排序了,所以只能减去这个奖励了 { sum-=std[i].y; } } printf("%lld\n",sum); return 0; }之后我用优先队列做了一遍对时间从小到大排序,之后进行模拟#include<iostream> #include<cstring> #include<cstdio> #include<algorithm> #include<queue> using namespace std; struct node { int x,y; }; bool cmp(node n,node m) { return n.x<m.x; } priority_queue<int,vector<int>,greater<int> >que; int main() { int n,m; struct node std[50001]; int i,j; scanf("%d",&n); for(i=0;i<n;i++) { scanf("%d %d",&std[i].x,&std[i].y); } long long ans=0; sort(std,std+n,cmp); for(i=0;i<n;i++) { int k=std[i].y; if(std[i].x>que.size()) { ans+=k; que.push(k); } else { ans+=k; que.push(k); int min1=que.top(); ans-=min1; que.pop(); } } printf("%lld\n",ans); return 0; }
转载请注明原文地址: https://www.6miu.com/read-1100163.html

最新回复(0)