有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 <bits/stdc++.h> using namespace std; typedef long long ll; priority_queue<int,vector<int>,greater<int> >q; int n; struct node{int t,w;bool operator<(const node &a) const {return a.t>t;} }e[50006]; int main() {scanf("%d",&n);for(int i=0;i<n;i++)scanf("%d%d",&e[i].t,&e[i].w);sort(e,e+n);ll ans=0;for(int i=0;i<n;i++){if(e[i].t>q.size()){ans+=e[i].w;q.push(e[i].w);}else{ans+=e[i].w;q.push(e[i].w);ans-=q.top();q.pop();}}printf("%lld\n",ans);return 0; }

?

轉載于:https://www.cnblogs.com/shinianhuanniyijuhaojiubujian/p/9569407.html

新人創作打卡挑戰賽發博客就能抽獎！定制產品紅包拿不停！

總結

以上是生活随笔為你收集整理的1163 最高的奖励（贪心+优先队列）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。