贪心构造专题

DEV3937 / 2024-09-27 / 原文

ABC137D Summer Vacation

给你 $n$ 个工作，$(a_i,b_i)$ 表示工作 $i$ 需要花费 $a_i$ 天，收益为 $b_i$，每天只能做一个，求 $m$ 天内得到的最大收益。

$n,m\le 10^5$

考虑带悔贪心，先按 $a_i$ 为第一关键字，$b_i$ 为第二关键字排序，若 $m-cnt\ge a_i$ 则把 $i$ 扔进堆里，否则就考虑把堆里最小的元素扔掉直到满足条件，再把 $i$ 放进堆里，每步求最优答案，时间复杂度 $O(n\log n)$。

code

#include<bits/stdc++.h>
using namespace std;
const int maxn=2e5+3;
int n,m;
struct node{
    int a,b;
    bool operator<(const node o)const{
        if(a!=o.a) return a>o.a;
        return b<o.b;
    }
}a[maxn];
struct nodee{
    int a,b;
    bool operator<(const nodee o)const{
        if(b!=o.b) return b>o.b;
        return a>o.a;
    }
};
priority_queue<nodee>q;
int ans,sum,cnt;
signed main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        cin>>a[i].a>>a[i].b;
    }
    sort(a+1,a+n+1);
    for(int i=1;i<=n;i++){
        int tot=0;
        if(m-cnt>=a[i].a){
            q.push({a[i].a,a[i].b});
            cnt++;
            sum+=a[i].b;
            ans=max(ans,sum);
        }else{
            while(!q.empty()&&m-cnt<a[i].a&&tot+q.top().b<=a[i].b){
                tot+=q.top().b;
                sum-=q.top().b;
                cnt--;
                q.pop();
            }
            if(m-cnt>=a[i].a){
                q.push({a[i].a,a[i].b});
                cnt++;
                sum+=a[i].b;
            }
            ans=max(ans,sum);
        }
    }

    cout<<ans<<'\n';
    return 0;
}