題干：

有N個任務(wù)，每個任務(wù)有一個最晚結(jié)束時間以及一個對應(yīng)的獎勵。在結(jié)束時間之前完成該任務(wù)，就可以獲得對應(yīng)的獎勵。完成每一個任務(wù)所需的時間都是1個單位時間。有時候完成所有任務(wù)是不可能的，因為時間上可能會有沖突，這需要你來取舍。求能夠獲得的最高獎勵。

Input

第1行：一個數(shù)N，表示任務(wù)的數(shù)量(2 <= N <= 50000)?
第2 - N + 1行，每行2個數(shù)，中間用空格分隔，表示任務(wù)的最晚結(jié)束時間Eii以及對應(yīng)的獎勵Wii。(1 <= Eii?<= 10^9，1 <= Wii?<= 10^9)

Output

輸出能夠獲得的最高獎勵。

Sample Input

7 4 20 2 60 4 70 3 40 1 30 4 50 6 10

Sample Output

230

解題報告：

? ? 爛大街的優(yōu)先隊列貪心就不再贅述了、、、這題偶然發(fā)現(xiàn)可以并查集你敢信，，，首先按照權(quán)值排序，然后遍歷找到可以最早進行該任務(wù)的時間，用并查集來合并這個時間并且找到可以執(zhí)行這個時間的最晚時間（也就是在這一步貪心了），因為對于這個任務(wù)，肯定越晚完成越好，因為可以留更多的時間給其他的任務(wù)。然后如果實在找不到時間了那就GG了，這個任務(wù)不能選了。因為有其他更優(yōu)秀的任務(wù)占據(jù)了這個時間，整個過程用并查集維護。

AC代碼：

#include<bits/stdc++.h> #define ll long long #define fi first #define se second using namespace std; const int MAX = 50000 + 5; ll f[MAX]; pair <ll,ll> p[MAX];int find(int x){if(x<=0) return -1; if(x==f[x]) return f[x]=x-1; else return f[x] = find(f[x]); } int main() {ll n,sum=0;cin>>n;for(int i = 1; i<=n; i++){f[i]=i;scanf("%d%d",&p[i].se,&p[i].fi);p[i].fi=-p[i].fi;}sort(p+1,p+n+1);for(int i = 1; i<=n; i++){if(find(p[i].se)>=0) sum += (-p[i].fi);}printf("%lld\n",sum);return 0; }

優(yōu)先隊列AC代碼：

//按起點排序，優(yōu)先隊列維護 #include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #include<queue> using namespace std; struct Node {int t,w; } node[50000 + 18]; bool cmp(const Node & a,const Node & b) {if(a.t!=b.t) return a.t<b.t;else return a.w<b.w; } priority_queue <int,vector<int>,greater<int> > pq; int main() {int n;int maxtime,cur=0;long long ans=0;cin>>n;for(int i = 0; i<n; i++) {scanf("%d %d",&node[i].t,&node[i].w);maxtime=max(maxtime,node[i].t); }sort(node,node+n,cmp);for(int i = 0;i<n; i++)if(cur < node[i].t) {pq.push(node[i].w);cur++;}else if(cur == node[i].t) {if(node[i].w > pq.top() ) {pq.pop();pq.push(node[i].w);}}while(!pq.empty() ) {ans+=pq.top();pq.pop();}printf("%lld\n",ans);return 0 ; }

?

總結(jié)

以上是生活随笔為你收集整理的【51Nod - 1163】最高的奖励 （贪心+优先队列 或 妙用并查集）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。