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

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;
}
This post is licensed under CC BY 4.0 by the author.