题解：P12360 [eJOI 2024] 足球决斗 / CF Duels

· · 题解

首先，答案是可二分的，如果检查了前 k 个足球馆即能保证必胜，那么多检查几个仍能确保必胜。

考虑如何检查答案的可行性。

能确保必胜，当且仅当在最坏情况下仍然能够取胜。

对于本题而言，最坏情况就是敌队经理足够明智，采取了最优策略。换位思考一下，他一定把战斗力高的放在奖金高的体育馆，这样赢得奖金最高的比赛的胜算最大。简单证明一下，若他没有这样做，放弃了最高奖金的比赛，那么这名球员至多赢得另一场比赛的奖金，必然无法造成最优的贡献。

也就是说，在后面的没有确定的比赛中，敌队经理会按照比赛场馆奖金从高到低的顺序，依次放入手头上最强的球员，次强的，依此类推。

于是，最坏情况下敌方球员排布已经得知。思考我方如何应对。

我们按照奖金从高到低的顺序考虑，如果我方手上有能够击败对方的球员，那么一定要出动这名球员，理由和刚才一样，如果放弃了这场比赛，那么他只能获得一场更低奖金的比赛，不优。

具体地，将每场比赛按照奖金从高到低遍历，找到战力高于对方且战力最低的球员，即以最小损耗获得奖金，若没有高于对方的球员，即放弃奖金。

实现方面使用 multiset 比较好。

AC 代码：

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N=5e4+50;
int T,n;
int a[N],b[N],p[N];
int L,R,mid,res,sma,smb;
multiset<int>s;
multiset<int>::iterator it;
struct node{
    int p;
    int b;
}tmp[N];
int tb[N];
bool cmp(node x,node y){
    return x.p<y.p;
}
bool cmp2(node x,node y){
    return x.p>y.p;
}
bool check(int x){
    s.clear();
    sma=0;
    smb=0;
    for(int i=1;i<=x;i++){
        tmp[i].b=b[i];
        tmp[i].p=p[i];
    }
    for(int i=x+1;i<=n;i++) tmp[i].p=p[i];
    sort(tmp+x+1,tmp+n+1,cmp);
    for(int i=x+1;i<=n;i++) tb[i]=b[i];
    sort(tb+x+1,tb+n+1);
    for(int i=x+1;i<=n;i++) tmp[i].b=tb[i];
    sort(tmp+1,tmp+n+1,cmp2);
    for(int i=1;i<=n;i++) s.insert(a[i]);
    for(int i=1;i<=n;i++){
        it=s.upper_bound(tmp[i].b);
        if(it==s.end()){
            smb+=tmp[i].p;
            it=s.lower_bound(0);
            s.erase(it);
            continue;
        }
        sma+=tmp[i].p;
        s.erase(it);
    }
    return sma>smb;
}
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin>>n;
    for(int i=1;i<=n;i++) cin>>p[i];
    for(int i=1;i<=n;i++) cin>>b[i];
    for(int i=1;i<=n;i++) cin>>a[i];
    sort(a+1,a+n+1);
    L=0;
    R=n;
    res=-1;
    while(L<=R){
        mid=(L+R)>>1;
        if(check(mid)){
            R=mid-1;
            res=mid;
        }else L=mid+1;
    }
    cout<<res<<'\n';
    return 0;
}