2020 贪吃蛇 · 方案一 multiset 模拟

CSP-S 标程 · 复赛真题 · 代码 · cpp · 难度 4/5 · 共 2211 字
n 条蛇（力量值，不降序给出）
2020
贪心
正文

// CSP-S 2020 复赛 T4 · 贪吃蛇（方案一：multiset 逐轮模拟，部分分）
// 原题：https://oj.yecheng.tv/p/CSPS2020D
// 题意：n 条蛇（力量值，不降序给出）。每轮：最强蛇吃完最弱蛇，变成
//       |max − min|；若吃完后它不是剩下的蛇中最强的（有并列则按"它
//       是否会立刻被吃"决定），它可以选择不吃。所有蛇都理性（先保命
//       再吃蛇），求最终剩多少条蛇。T 组，每组以修改后的力量重置。
// 思路（multiset 模拟）：
//   每轮：
//   1. 取最强 mx、最弱 mn；
//   2. 算吃完后新值 w = mx − mn；
//   3. 判定：移除 mx、mn，加入 w 后，w 是否严格大于剩余最大（或并列
//      时按处境判断）→ 不安全则本轮"不吃"，游戏结束；
//   4. 安全则吃（t = 剩余条数减一）。
//   multiset 天然有序，插入删除 O(log n)；n ≤ 1e6 时 log 也很大，
//   但配合"一旦进入安全阶段就一路吃到剩 1~2 条"的性质（方案二），
//   方案一纯模拟在 55% 数据（n ≤ 2e3）内稳过。
// 复杂度：O(轮数 · log n)，最坏 O(n log n)。
// 易错点：
//   1. 并列最强时"吃掉的先后"按输入顺序（题面：最小编号的强蛇先吃）；
//   2. w = 0 的新蛇是并列最强 → 它下一轮可能被吃，需要按处境判断；
//   3. T 组之间完全独立。
#include <cstdio>
#include <set>
using namespace std;

int T;
multiset<int> s;
int val[1000005];                      // 每条蛇当前力量（供修改）

int main() {
    freopen("snakes.in", "r", stdin);
    freopen("snakes.out", "w", stdout);
    scanf("%d", &T);
    for (int tc = 1; tc <= T; tc++) {
        int n;
        if (tc == 1) {
            scanf("%d", &n);
            s.clear();
            for (int i = 0; i < n; i++) {
                int x;
                scanf("%d", &x);
                val[i + 1] = x;
                s.insert(x);
            }
        } else {
            int kk;
            scanf("%d", &kk);
            for (int j = 0; j < kk; j++) {
                int p, v;
                scanf("%d%d", &p, &v);
                // 第 p 条蛇改为 v：先删旧值再插新值
                s.erase(s.find(val[p]));
                val[p] = v;
                s.insert(v);
            }
        }
        // 模拟
        while ((int)s.size() >= 2) {
            int mx = *s.rbegin();
            int mn = *s.begin();
            int w = mx - mn;
            s.erase(s.find(mx));
            s.erase(s.find(mn));
            if (s.empty()) {
                s.insert(w);
                break;
            }
            int restMax = *s.rbegin();
            // w 吃完后若不再是最强（w < restMax）或并列被吃 → 不吃
            if (w < restMax) {
                s.insert(mx);
                s.insert(mn);
                break;
            }
            s.insert(w);
        }
        printf("%d\n", (int)s.size());
    }
    return 0;
}
2020 贪吃蛇 · 方案一 multiset 模拟

正文

CSP-S 标程 · 复赛真题的其它内容
