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

Claire0918 · 2025-11-27 19:40:08 · 题解

不难发现能否胜利显然满足单调性，考虑二分确定的前缀长度。显然能保证胜利当且仅当对方采取最优策略时仍然能胜利，而对方的最优策略显然是在剩下的未确定的位置中价值尽量大的放入技能等级尽量高的球员，仅需对这一种情况考虑能否胜利。

我们很难不注意到如果放弃一局的胜利，最多仅能获得另外一局的胜利，于是我们将所有位置按照价值从高到低考虑，如果可以胜利（即目前剩下的最高等级大于对方在这一位置球员的等级）就放置最小的大于对方在这一位置等级的球员，否则放置哪个都一样，显然放最小的。按照如上方式算出最终能获得的最大价值，判一下即可。使用 multiset 维护剩下的球员等级，时间复杂度 \mathcal{O}(n\log^2n)。

Code：

#include<bits/stdc++.h>
#define mem(a, v) memset(a, v, sizeof(a))

using namespace std;

const int maxn = 5e4 + 10;

int n;
long long sum = 0;
int a[maxn], b[maxn], c[maxn], p[maxn];
priority_queue<int> q;
priority_queue<pair<int, int> > q2;
multiset<int> st;

inline bool check(int x){
    for (int i = 1; i <= x; i++){
        c[i] = b[i];
    }
    for (int i = x + 1; i <= n; i++){
        q.push(b[i]), q2.push(make_pair(p[i], i));
    }
    for (;!q.empty(); c[q2.top().second] = q.top(), q.pop(), q2.pop());
    for (int i = 1; i <= n; i++){
        q2.push(make_pair(p[i], i)), st.insert(a[i]);
    }
    long long res = 0;
    while (!q2.empty()){
        const int pos = q2.top().second;
        if (c[pos] > *st.rbegin()){
            st.erase(st.begin());
        }else{
            res += q2.top().first, st.erase(st.lower_bound(c[pos]));
        }
        q2.pop();
    }
    return res > sum - res;
}

int main(){
    scanf("%d", &n);
    for (int i = 1; i <= n; i++){
        scanf("%d", &p[i]), sum += 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 + 1;
    while (l < r){
        const int mid = l + r >> 1;
        if (check(mid)){
            r = mid;
        }else{
            l = mid + 1;
        }
    }
    printf("%d", l == n + 1 ? -1 : l);

return 0;
}