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

_Mortis_ · 2025-10-04 15:29:33 · 题解

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

显然答案具有二分性。

现在我们需要判断当前的 mid 是否可行，即写 check 函数。

考虑我方最劣情况（对方的最优情况），即在后 n - mid 个球场，对方将技能等级按奖金顺序排列（最强的的对应奖金最多的）。

此时我方可以使用类似田忌赛马的思路，优先考虑奖金最大的场地，如果我方等级最高的都干不过，就用最低的干。否则用等级比对方高的人中等级最低的人干。可以用 set 中的 upper_bound 实现。

check 函数 O(n \log n) ，总时间复杂度 O(n \log ^2 n) 。

:::success[code]

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e5+10;
int T,n;
ll p[N],P[N];
int a[N],b[N],B[N];
set<int>A;
struct node{
    int p,b;
    friend bool operator < (const node &x,const node &y){
        return x.p>y.p;
    }
}C[N];
bool check(int x){
    for(int i=x+1;i<=n;i++)P[i]=p[i],B[i]=b[i];
    sort(P+x+1,P+n+1);
    sort(B+x+1,B+n+1);
    for(int i=1;i<=x;i++)C[i]=node{p[i],b[i]};
    for(int i=x+1;i<=n;i++)C[i]=node{P[i],B[i]};
    sort(C+1,C+n+1);
    for(int i=1;i<=n;i++)A.insert(a[i]);
    ll sum1=0,sum2=0;
    for(int i=1;i<=n;i++){
        auto p=A.upper_bound(C[i].b);//找比对方高的人中最低的
        if(p==A.end()){
            sum2+=C[i].p;
            A.erase(A.begin());
        }
        else{
            sum1+=C[i].p;
            A.erase(p);
        }
    }
    return sum1>sum2;
}
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++)scanf("%lld",&p[i]);
    for(int i=1;i<=n;i++)scanf("%d",&b[i]);
    for(int i=1;i<=n;i++)scanf("%d",&a[i]);
    int l=0,r=n,mid,ans=-1;
    while(l<=r){
        mid=l+r>>1;
        if(check(mid)){
            ans=mid;
            r=mid-1;
        }
        else l=mid+1;
    }
    printf("%d\n",ans);
    return 0;
}

:::