题解：P11328 [NOISG 2022 Finals] Gym Badges

ycy1124 · 2025-01-24 16:34:33 · 题解

题意

题面很详细，注意一下是先过关再升级。

思路

很一眼的返回贪心，难点在于开始时的排序。

首先很容易被题目误导想到按 l_i 从小到大排序，可这是错的。因为你通过的最后一个比赛并不需要通过后等级尽量小，所以会错。

考虑换一种排序方式，按 x_i+l_i 从小到大排序。证明：当你什么时候会更换两场比赛的顺序呢。显然是你先选上一场比赛就无法比下一场，交换后两场都可以比。这种情况即 x_i+sum>l_j 且 x_j+sum<l_i，也就等于按 x_i+l_i 排序。

接下来考虑反悔贪心，当当前这一个比赛无法满足时，显然替换掉前面比赛中 x 值最大的一场，于是可以拿个大根堆来维护。

代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
struct Node{
    int x,l;
}a[500005];
int b[500005];
int n,tot,sum;
inline bool cmp(Node x1,Node x2){
    return x1.l+x1.x<x2.l+x2.x;
}
inline void work1(int x){
    if(x*2+1<=tot&&b[x*2+1]>b[x]&&b[x*2]<b[x*2+1]){
        swap(b[x],b[x*2+1]);
        work1(x*2+1);
    }
    else if(x*2<=tot&&b[x*2]>b[x]){
        swap(b[x*2],b[x]);
        work1(x*2);
    }
}
inline void work(int x){
    if(x!=1&&b[x]>b[x/2]){
        swap(b[x],b[x/2]);
        work(x/2);
    }
}
signed main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i].x;
    }
    for(int i=1;i<=n;i++){
        cin>>a[i].l;
    }
    sort(a+1,a+n+1,cmp);
    for(int i=1;i<=n;i++){
        if(sum>a[i].l){
            if(b[1]>a[i].x){
                swap(b[1],b[tot]);
                sum-=b[tot];
                --tot; 
                work1(1);
                b[++tot]=a[i].x;
                sum+=b[tot];
                work(tot);
            }
        }
        else{
            sum+=a[i].x;
            b[++tot]=a[i].x;
            work(tot);
        }
    }
    cout<<tot;
    return 0;
}

AC 记录。