题解归档 - cf104118F

本文由 cf-code 本地题解库自动归档；公开内容以本地 AC/验证版本为准。

• 本地编号：cf104118F
• 本地来源：problems/cf104118F/idea.md
• 题目链接：https://codeforces.com/gym/104118/problem/F
• 原始标题：Gym 104118F - Factions vs The Hegemon

思路

Gym 104118F - Factions vs The Hegemon

Maintain the current live factions as a linked list.

At every step:

• Let total be the current total wealth.
• The civilization is in hegemony iff 2 * max_wealth > total.
• If not in hegemony, remove the west-most maximum.
• If in hegemony, remove the west-most minimum.
• Add floor(removed_wealth / 2) to each existing live neighbor.

Two ordered sets maintain:

• (wealth, index) for west-most minimum;
• (-wealth, index) for west-most maximum.

Neighbor updates delete/reinsert the affected nodes in both sets.

Complexity: O(n log n).

Checks:

• official sample 1
• statement sample 2 reconstructed from PDF
• randomized brute force for small n

代码

来源：problems/cf104118F/solution.cpp

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;
    vector<ll> w(n + 2);
    ll total = 0;
    for (int i = 1; i <= n; ++i) {
        cin >> w[i];
        total += w[i];
    }

    vector<int> pre(n + 2), nxt(n + 2);
    for (int i = 1; i <= n; ++i) {
        pre[i] = i - 1;
        nxt[i] = i + 1;
    }
    nxt[n] = 0;

    set<pair<ll, int>> mn, mx;
    for (int i = 1; i <= n; ++i) {
        mn.insert({w[i], i});
        mx.insert({-w[i], i});
    }

    auto erase_node = [&](int id) {
        mn.erase({w[id], id});
        mx.erase({-w[id], id});
    };
    auto insert_node = [&](int id) {
        mn.insert({w[id], id});
        mx.insert({-w[id], id});
    };
    auto add_to = [&](int id, ll delta) {
        if (id == 0) return;
        erase_node(id);
        w[id] += delta;
        insert_node(id);
    };

    for (int alive = n; alive >= 1; --alive) {
        auto [neg_max_w, max_id] = *mx.begin();
        ll max_w = -neg_max_w;
        int id;
        if (max_w * 2 > total) {
            id = mn.begin()->second;
        } else {
            id = max_id;
        }

        ll cur = w[id];
        cout << id << ' ' << cur << '\n';

        erase_node(id);
        total -= cur;

        int L = pre[id], R = nxt[id];
        if (L) nxt[L] = R;
        if (R) pre[R] = L;

        ll give = cur / 2;
        if (L) total += give;
        if (R) total += give;
        add_to(L, give);
        add_to(R, give);
    }

    return 0;
}