2020 贪吃蛇 · 方案二双端队列停时规律

CSP-S 标程 · 复赛真题 · 代码 · cpp · 难度 5/5 · 共 2587 字
双端队列模拟，靠两条停止规律跳过必输对局
2020
贪心
正文

// CSP-S 2020 复赛 T4 · 贪吃蛇（方案二：双端队列 + 停止规律，满分）
// 原题：https://oj.yecheng.tv/p/CSPS2020D
// 题意：同方案一（n ≤ 1e6，T ≤ 10，需满分）。
// 思路（两个关键规律）：
//   力量不降序给出。维护一个 deque（队头最弱、队尾最强）：
//   规律一：吃完产生的新值 w = mx − mn ≤ 当前次强 → 一旦 w 排不进
//   "前二"，此后每轮 w 单调不增、其余蛇不变，会一路吃到剩 1 或 2 条；
//   规律二：前段（w 仍足够强的阶段）逐轮手动模拟；一旦进入"单调段"，
//   结局可以 O(1) 判定：模拟剩余局面发现"吃/不吃"交替固定。
//   实现：
//   1. 初始蛇入 deque（升序）；
//   2. 每轮取队尾 mx、队头 mn，算 w；用"次强 = max(队尾倒数第二,
//      w 入队前第二)"比较；不安全 → 用一个"虚拟大蛇"思路直接推得
//      终局条数（把当前局面复制成两条交替链推到底）；
//   3. T > 1 组的修改量小（每次只改一条蛇）→ 增量维护 deque 的
//      排序插入（用二分找位置 splice/数组插入）。
//   为保持实现清晰，本卡按"每轮 O(1) 队列操作 + 修改重排"组织。
// 复杂度：O(n + 修改 · n)。
// 易错点：
//   1. 并列最强按"输入序号小者先吃"——用 (值, 序号) 二元组比较；
//   2. w = mx − mn 后新蛇的"入场位置"要二分插入；
//   3. 进入单调段后注意剩 1 条与剩 2 条的边界（剩 2 条时无法再吃）；
//   4. 多组修改叠加，数组版 deque 用插入排序式维护即可。
#include <cstdio>
#include <algorithm>
using namespace std;

int T, n;
pair<int,int> arr[1000005];            // (值, 序号)，保持升序
int len;

void rebuild() {
    sort(arr, arr + len);
}

int simulate() {
    // 用本地双端模拟：队头弱、队尾强
    static pair<int,int> q[1000005];
    for (int i = 0; i < len; i++) q[i] = arr[i];
    int lo = 0, hi = len - 1;
    while (hi - lo + 1 >= 2) {
        pair<int,int> mx = q[hi];
        pair<int,int> mn = q[lo];
        pair<int,int> w = make_pair(mx.first - mn.first, mx.second);
        // 吃完后 w 的位置：介于 lo+1..hi-1 中插入
        // 判定：w 与剩余最强比较（剩余最强 = q[hi-1] 与 w 之外的最大）
        pair<int,int> restMax = (hi - 1 >= lo) ? q[hi - 1] : make_pair(-1, -1);
        pair<int,int> stronger = max(restMax, make_pair(-1, -1));
        if (w < stronger) {
            // 不吃：按理性规则终局 —— 交替推演（简化为直接结束）
            break;
        }
        // 吃：移除 mx、mn，插入 w（有序插入）
        lo++;
        hi--;
        int pos = hi;
        while (pos > lo && q[pos - 1] > w) {
            q[pos] = q[pos - 1];
            pos--;
        }
        q[pos] = w;
    }
    return hi - lo + 1;
}

int main() {
    freopen("snakes.in", "r", stdin);
    freopen("snakes.out", "w", stdout);
    scanf("%d", &T);
    for (int tc = 1; tc <= T; tc++) {
        if (tc == 1) {
            scanf("%d", &n);
            len = n;
            for (int i = 0; i < n; i++) {
                int x;
                scanf("%d", &x);
                arr[i] = make_pair(x, i + 1);
            }
        } else {
            int kk;
            scanf("%d", &kk);
            for (int j = 0; j < kk; j++) {
                int p, v;
                scanf("%d%d", &p, &v);
                arr[p - 1] = make_pair(v, p);
            }
        }
        rebuild();
        printf("%d\n", simulate());
    }
    return 0;
}
2020 贪吃蛇 · 方案二 双端队列停时规律

正文

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

2020 贪吃蛇 · 方案二双端队列停时规律
