POJ - 1456 贪心 堆常用操作 注意细节

题意:给定n个商品的deadline和profit,求每天卖一件的情况下的最大获利

显然是一道贪心

按deadline从小到大排序好,动态维护小根(profit)堆的大小<=当前deadline的天数,往里面符合条件的尽可能塞更优解

注意有n为0的情况

/*H E A D*/
struct Node{
    ll p,d,id;
}a[maxn];

bool cmp(Node a,Node b){
    if(a.d!=b.d)return a.d<b.d;
    return a.p>b.p;
}
ll n;
int main(){
    while(cin>>n){  
        ll day=0;
        priority_queue<ll,vector<ll>,greater<ll> > que; 
        while(!que.empty())que.pop();
        rep(i,1,n){
            a[i].p=read();
            a[i].d=read();
            a[i].id=i;
            day=max(day,a[i].d);
        }
        if(n==0){
            println(0);
            continue;
        }
        sort(a+1,a+1+n,cmp);
        ll ans=0;
        int now=1;
        rep(i,1,day){
            while(a[now].d<i) now++;
            while(a[now].d==i&&que.size()<i&&now<=n){//equal!!!!
                que.push(a[now].p);now++;
            }
            while(a[now].d==i&&que.size()==i&&now<=n&&que.top()<a[now].p){
                que.pop();
                que.push(a[now].p);
                now++;
            }
        }
        while(!que.empty()){
            ans+=que.top();
            que.pop();
        }
        println(ans);
    }
    return 0;
}