题解：P11328 [NOISG 2022 Finals] Gym Badges

· · 题解

题目的条件可以转化为：如果你参加这个比赛，让自己的等级提升 X_i 并获得一个徽章后，你的等级小于等于 L_i+X_i，那么你可以参加这个比赛。

所以，先对 L_i+X_i 从小到大排序。然后顺序遍历选比赛，如果可以选则选，否则一定要放弃一个比赛，由于每个比赛的贡献相同，那我们就放弃 X_i 最大的那个比赛。这个过程可以用一个大根堆（优先队列）来维护。

:::info[参考代码]

//Author: mairuisheng
//#pragma GCC optimize(3)
#include<cstdio>
#include<queue>
#include<algorithm>
#define int long long
using namespace std;
inline int read()
{
    int x=0,f=1;
    char s;
    s=getchar();
    while(s<48||s>57)
    {
        if(s=='-')f=-f;
        s=getchar();
    }
    while(s>47&&s<58)
    {
        x=(x<<3)+(x<<1)+s-48;
        s=getchar();
    }
    return x*f;
}
constexpr int N=5e5+1;
struct Node
{
    int tim,lim;
}a[N];
int n;
int ans;
priority_queue<int> q;
bool Cmp(Node x,Node y)
{
    return x.lim<y.lim;
}
void Solve()
{
    sort(a+1,a+1+n,Cmp);
    int i,sum=0;
    for(i=1;i<=n;++i)
    {
        q.push(a[i].tim);
        sum+=a[i].tim;
        if(sum<=a[i].lim)++ans;
        else
        {
            sum-=q.top();
            q.pop();
        }
    }
}
signed main()
{
    n=read();
    int i;
    for(i=1;i<=n;++i)a[i].tim=read();
    for(i=1;i<=n;++i)a[i].lim=read()+a[i].tim;
    Solve();
    printf("%lld",ans);
    return 0;
}

:::

  1. P4053 [JSOI2007] 建筑抢修。
  2. P11457 [USACO24DEC] Job Completion G。