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

ELECTRODE_kaf · 2025-05-01 13:03:04 · 题解

显然得到的信息越多越容易确定胜利，因此答案具有单调性，考虑二分并检验得到信息的场馆数量 mid。

因为我们可以在比赛开始后再安排双方球员的对阵关系，所以不确定性来源于一对对阵取得的收益来自哪个场馆不确定。然后就是经典的田忌赛马策略：将双方球员和场馆按权值升序排列，逐一考虑己方队员，考虑他能战胜的所有对手并分情况讨论。若选择的对手来自已知的场馆那么收益是确定的，这种情况容易处理。若选择的对手来自未知的场馆，则取其中的最小收益累加。考虑完所有球员后判断能否取得冠军。若最小收益足以战胜对手则说明能否获胜与对方的安排无关，可以必胜，因为我们考虑了对方采取最佳的安排将我方收益最小化时的情况。

用一个大根堆维护所有可能的对阵情况，每次取出堆顶对阵方案即可。

const ll N = 5e4 + 10;
ll n, sum, a[N], v[N];
pll sta[N], player[N];
pqueue(ll, less) pq;

#define jump1 for(;a[i]>player[p1].fi and p1<=n;p1++)
#define jump2 while(sta[p2].se<=k and p2<=n)p2++;

bool check(ll k) {
    myclear(pq);
    ll pts = 0, p1 = 1, p2 = 1;
    jump2;

    rep(i, 1, n) {
        jump1{
            if (player[p1].se <= k)
                pq.push(v[player[p1].se]);
            else {
                pq.push(sta[p2].fi);
                p2++;
                jump2;
            }
        }

        if (pq.size()) {
            pts += pq.top();
            pq.pop();
        }
    }

//  cout << "pts=" << pts << '\n';
//  pause;
    return pts > sum - pts;
}

int main() {
    cin >> n;

    rep(i, 1, n) {
        cin >> v[i];
        sta[i] = {v[i], i};
        sum += v[i];
    }

    sort(sta + 1, sta + n + 1);

    rep(i, 1, n) {
        cin >> player[i].fi;
        player[i].se = i;
    }

    sort(player + 1, player + n + 1);

    rep(i, 1, n) cin >> a[i];

    sort(a + 1, a + n + 1);

    ll l = 0, r = n, ans = -1;

    while (l <= r) {
        ll mid = (l + r) / 2;

        if (check(mid)) {
            ans = mid;
            r = mid - 1;
        } else
            l = mid + 1;
    }

    cout << ans;
}