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

· · 题解

首先发现答案具有单调性，因为如果在第 x 场对决之后就有了必胜策略，也就代表着对面在第 x 场对决后无论怎么安排都无法获胜，所以在第 x+1 场对决后肯定还有必胜策略。

于是可以二分答案，考虑如何判断答案的正确性，显然要贪心，因为对方不知道我们的出场顺序，所以肯定贪心的在价值高的球馆放强的球员，于是对方的出场顺序确定了，那我方的出场顺序也就很显然了，还是按球馆的价值从大到小考虑，如果我方有球员能够击败对方，那就放能击败对方的球员中最弱的，这样不会浪费。为了快速找到球员，我们维护前缀最大值，线段树上二分即可。



#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 5e4 + 5;
const int inf = 1000000000000000;
int n, p[N], a[N], b[N], f[N], g[N], tree[N << 2], ans = - 1, sum;
struct Node{
    int p, a;
}c[N];
bool cmp (Node a, Node b){
    if (a.p != b.p) return a.p > b.p;
    return a.a > b.a;
}
void pushup (int x){
    tree[x] = max(tree[(x << 1)], tree[(x << 1) + 1]);
    return ;
}
void build (int l, int r, int x){
    if (l == r){
        tree[x] = a[l];
        return ;
    }
    int mid = l + r >> 1;
    build(l, mid, (x << 1)), build(mid + 1, r, (x << 1) + 1);
    pushup(x);
    return ;
}
int query (int l, int r, int cur, int val){
    if (l == r) return l;
    int mid = l + r >> 1;
    if (tree[(cur << 1)] > val) return query(l, mid, (cur << 1), val);
    else return query(mid + 1, r, (cur << 1) + 1, val);
}

void update (int l, int r, int x, int cur, int val){
    if (l > x || r < x) return ;
    if (l == x && r == x){
        tree[cur] = val;
        return ;
    }
    int mid = l + r >> 1;
    update(l, mid, x, (cur << 1), val), update(mid + 1, r, x, (cur << 1) + 1, val);
    pushup(cur);
    return ;
}
bool chk (int x){
    for (int i = 1; i <= n; ++ i) f[i] = p[i], g[i] = b[i];
    sort(f + x + 1, f + n + 1), sort(g + x + 1, g + n + 1);
    for (int i = 1; i <= n; ++ i) c[i] = (Node){f[i], g[i]};
    sort(c + 1, c + n + 1, cmp);
    int tp = 0, L = 1, R = n, pos;
    build(1, n, 1);
    for (int i = 1; i <= n; ++ i){
        if (tree[1] <= c[i].a) pos = - 1;
        else pos = query(1, n, 1, c[i].a);
        if (pos > 0) tp += c[i].p, update(1, n, pos, 1, - inf);
    }
    return tp > sum - tp;
}
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], sum += 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);
    int l = 0, r = n;
    while (l <= r){
        int mid = l + r >> 1;
        if (chk(mid)) ans = mid, r = mid - 1;
        else l = mid + 1;
    }
    cout << ans << '\n';
    return 0;
}