题解 P2949 【[USACO09OPEN]工作调度Work Scheduling】

witliu · 2017-07-22 10:10:20 · 题解

贪心思想：先假设每一项工作都做，将各项工作按截止时间排序后入队，在判断第i项工作做与不做时，若其截至时间符合条件，则将其与队中报酬最小的元素比较，若第i项工作报酬较高，则ans+=a[i].p-q.top()。用优先队列（小根堆）来维护队首元素最小。

#include <queue>
#include <cstdio>
#include <algorithm>
using namespace std;
struct yw{
long long d,p;
}a[100005];
priority_queue <yw> q;
bool cmp(const yw&a,const yw&b)
{
  return a.d<b.d;
}
bool operator < (yw a,yw b)
{
     return a.p>b.p;
}
int main()
{    
    long long n,ans=0;
    scanf("%lld",&n);
    for(int i=1;i<=n;i++) 
    scanf("%lld%lld",&a[i].d,&a[i].p);
    sort(a+1,a+1+n,cmp);  // 按照截止时间排序 
    for(int i=1;i<=n;i++)
        if (a[i].d<=q.size())
        {
          if (q.top().p<a[i].p) 
            ans+=a[i].p-q.top().p,q.pop(),q.push(a[i]);//修改队中元素 
        }
        else 
        q.push(a[i]),ans+=a[i].p;
    printf("%lld",ans);
}