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

Taduro · 2018-08-15 14:37:50 · 题解

这题是一道带反悔的贪心，第一次遇到这种思路的题赶紧发个题解纪念一下。 首先思路就是先按时间排序（不是那个1e8啊，是截止日期），然后如果一个工作有时间去做，就先做了它（听起来有点怪），然后把它的价值压入一个小根堆。当我们找到一个没法做却价值比当前堆顶高的工作时，我们就放弃那个最小的工作，用做它的时间去做这个价值更高的工作。

另外，这题似乎不能用一般的单调队列做？（求不打脸）因为维护队列单调性的时候要删去一些元素，这样就无法支持题目所要求的修改。（或者用dp+单调队列？）

#include<queue>
#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;
struct node{
    int tim,mny;
}w[100001];
int n,i;
long long ans;
priority_queue<int,vector<int>,greater<int> > q;
bool cmp(node a,node b){
    return a.tim<b.tim;
}
int main(){
    scanf("%d",&n);
    for (i=1; i<=n; i++)
        scanf("%d%d",&w[i].tim,&w[i].mny);
    sort(w+1,w+n+1,cmp);
    for (i=1; i<=n; i++){
        if (w[i].tim<=q.size()){
            if (w[i].mny>q.top()){
                ans-=q.top();
                q.pop(); q.push(w[i].mny);
                ans+=w[i].mny;
            }
        }
        else{
            q.push(w[i].mny);
            ans+=w[i].mny;
        }
    }
    printf("%lld",ans);
    return 0;
}