最高的奖励 - 优先队列&贪心 / 并查集

题目地址:http://www.51cpc.com/web/problem.php?id=1587

Summarize:

优先队列&贪心: 1. 按价值最高排序,价值相同则按完成时间越晚为先;

        2. 使用数组记录时间节点是否有任务,时间节点从最晚倒序遍历;

        3. 若此刻时间节点有任务,则从此时间节点往前推,直到某一刻无任务,否则放弃该任务;

附贪心代码:

(此处并未使用优先队列,以vector代替)

#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
#define LL long long const int N = 5e5+;
int n;
struct Task {
LL t,v;
bool operator<(const Task &a) {
return v == a.v? t>a.t: v>a.v;
}
};
vector<Task> task;
int vis[N]; int main()
{
ios::sync_with_stdio(false); while(cin>>n)
{
LL ans=, count=;
for(int i=; i<n; i++) {
vis[i]=;
LL t,v;
cin>>t>>v;
task.push_back(Task{t,v});
} sort(task.begin(), task.end());
for(int i=; i<n; i++) {
int t = task[i].t;
while(vis[t] && t) t--;
if(!t) continue; vis[t] = ;
ans += task[i].v;
if(++count == n)
break;
} cout<<ans<<endl;
task.clear();
} return ;
}
上一篇:poj2970 The lazy programmer 【优先队列】


下一篇:hdu3438 Buy and Resell(优先队列+贪心)