P2949 [USACO09OPEN]Work Scheduling G

3 
2 10 
1 5 
1 7 

17

后悔法的贪心。
首先思路就是先按截止日期排序，然后如果一个工作有时间去做，就先做了它，然后把它的价值压入一个小根堆。当我们找到一个没法做却价值比当前堆顶高的工作时，我们就放弃那个最小的工作（后悔了），用做它的时间去做这个价值更高的工作。

#include<iostream>
#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<queue>
#define ls (p<<1)
#define rs (p<<1|1)
#define mid (l+r)/2
#define over(i,s,t) for(int i=s;i<=t;++i)
#define lver(i,t,s) for(int i=t;i>=s;--i)
using namespace std;
typedef long long ll;//全用ll可能会MLE，ll比int占的内存大
const ll N=1e5+7;
//const ll INF=1e13+7;
//const ll mod=2147483647;
//const double EPS=1e-6;
ll ans;
ll n,m;
struct node
{
    ll d,p;
    bool operator<(const node& t)const{return d<t.d;}
}f[N];
priority_queue<ll,vector<ll>,greater<ll> >q;//维护最小值
int main()
{
    scanf("%d",&n);
    over(i,1,n)
    scanf("%d%d",&f[i].d,&f[i].p);
    sort(f+1,f+1+n);
    over(i,1,n)
    {
        if(f[i].d<=q.size())//q.size就代表着第几天
        {
            if(f[i].p>q.top())
            {
                ans+=f[i].p-q.top();
                q.pop();
                q.push(f[i].p);
            }
        }
        else {//总天数是很多的，所以每一件工作都可以做
            ans+=f[i].p;
            q.push(f[i].p);
        }
    }
    printf("%lld\n",ans);
    return 0;
}


有任何疑问欢迎评论哦虽然我真的很菜