自动搬运

查看原文

来自洛谷，原作者为

	ycy1124 ENTJ-A | 有事私。| 清关了，私信基本也不会回关（除非满足条件），但可以支持小号回关 | 出去玩去了。不在线。微信可能上。

搬运于2025-08-24 23:06:29，当前版本为作者最后更新于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 记录。