[BZOJ1572] [Usaco2009 Open]工作安排Job(贪心 + 堆)

传送门

把任务按照d排序

一次加入到堆中,如果当前放不进堆中,并且比堆中最小的大,

就从堆中弹出一个数,再把当前的数放进去

#include <queue>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define N 100001
#define LL long long using namespace std; int n;
LL ans;
priority_queue <LL, vector <LL>, greater <LL> > q; struct node
{
LL d, p;
}a[N]; inline LL read()
{
LL x = 0, f = 1;
char ch = getchar();
for(; !isdigit(ch); ch = getchar()) if(ch == '-') f = -1;
for(; isdigit(ch); ch = getchar()) x = (x << 1) + (x << 3) + ch - '0';
return x * f;
} inline bool cmp(node x, node y)
{
return x.d < y.d;
} int main()
{
int i, now = 0;
n = read();
for(i = 1; i <= n; i++)
a[i].d = read(), a[i].p = read();
sort(a + 1, a + n + 1, cmp);
for(i = 1; i <= n; i++)
if(q.size() < a[i].d) q.push(a[i].p);
else if(!q.empty() && a[i].p > q.top())
{
q.pop();
q.push(a[i].p);
}
while(!q.empty()) ans += q.top(), q.pop();
printf("%lld\n", ans);
return 0;
}

  

上一篇:[bzoj1572][Usaco2009 Open]工作安排Job_贪心_堆


下一篇:bzoj1572 [Usaco2009 Open]工作安排Job【贪心 堆】