最高的奖励 51Nod - 1163

最高的奖励 51Nod - 1163

先将数据存入数组 排序 终止时间小的在前 相等则奖励值大的在前

之后将数组元素依次入队 若遇到奖励值较大却终止时间已过的元素 则用其替换掉 之前已选的元素中奖励值最小的

因为每个已选元素的终止时间在其被选时都是未被超过的 因为已排序 所以后来的元素必定满足先前元素的时间限定

再用奖励值大的元素将其替换 就相当于在选取该元素的时间点改为选则奖励值大的元素

其实就是随时间流逝 你找到一个元素 你发现它更有价值 但是你在时间上已经错过了它 你就吃后悔药 回到过去 把当时选的价值小的元素扔掉 改为选这个价值更大的元素

#include #include #include using namespace std;struct node{ friend bool operator< (node n1,node n2) { if(n1.w==n2.w) { return n1.e>n2.e; } else { return n1.w>n2.w; } } int e; long long w;};bool cmp(node n1,node n2){ if(n1.e==n2.e) { return n1.w que; struct node tem[50001]; struct node cur; long long sum; int n,i,j,time; while(scanf("%d",&n)!=EOF) { for(i=1;i<=n;i++) { scanf("%d%lld",&tem[i].e,&tem[i].w); } sort(tem+1,tem+n+1,cmp); time=0,sum=0; for(i=1;i<=n;i++) { if(tem[i].e>time) { que.push(tem[i]); time++; } else { que.pop(); que.push(tem[i]); } } while(!que.empty()) { cur=que.top(); que.pop(); sum+=cur.w; } printf("%lld\n",sum); } return 0;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。