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

· · 题解

思路

首先我们明白，未被看到的体育场完全可以当作最劣情况考虑。那么最劣的情况奖金数量和对方的技能等级顺序排列。遂我们可以构造出看完前 k 个球场后最劣的情况：

随后考虑我方如何获得最大奖金。枚举我方能力小的到能力大的，用优先队列存储第 i 名球员可以成功获得奖金的体育场，把第 i 名球员安放到他打得过且奖金最高的场地即可。由于后面的球员一定也能前往前面的球员可以前往的体育场，因此正确性得以证明。

具体做法就是二分至多能看完的体育场数量 k，然后对于当前的 k 暴力构造出最劣的情况跑即可。构造情况和给球员找场地的复杂度为 O(n \log n)，总复杂度 O(n \log^2 n)。

代码

#include <bits/stdc++.h>
using namespace std;
#define int long long
int n, p[500005], a[500005], b[500005], x[500005], y[500005], l, r, sum, ans;
struct node {
    int p, b;
} c[500005];
bool cmp(node x, node y) {
    return x.b < y.b;
}
priority_queue<int, vector<int>, less<int>> q;//较大的元素会被优先取出 
bool check(int k) {
    int res = 0;
    while (!q.empty()) q.pop();
    for (int i = 1; i <= n; i++) {
        x[i] = p[i];
        y[i] = b[i];
    }
    sort(x + k + 1, x + n + 1);
    sort(y + k + 1, y + n + 1);
    for (int i = 1; i <= n; i++) {
        c[i] = {x[i], y[i]};
    }
    sort(c + 1, c + n + 1, cmp);
    for (int i = 1, j = 1; i <= n; i++) {
        while (c[j].b < a[i] && j != n + 1) {
            q.push(c[j++].p);//把所有打得过的放入优先队列 
        }
        if (!q.empty()) {
            res += q.top();
            q.pop();
        }//若没有可放的就让这个球员凑数就好了，因此不用计算贡献 
    }
    if (sum < res * 2) return 1;
    return 0;
}
signed main() {
    ios::sync_with_stdio(0);
    cin.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);
    if (!check(n)) {
        cout << "-1";
        return 0;
    }//特判无法获胜的情况 
    l = 0, r = n, ans = n;
    while (l <= r) {
        int mid = ((l + r) >> 1);
        if (check(mid)) {
            r = mid - 1;
            ans = mid;
        } else {
            l = mid + 1;
        }
    }
    cout << ans;
    return 0;
}