「CSP-S 2020」贪吃蛇

写一个在洛谷和牛客能过的想法，不知道过后会不会被hack掉

当前最强蛇会吃最弱蛇有三种可能

• 当前剩余蛇数量为2
• 最强蛇吃掉最弱蛇后不会变为最弱
• 最强蛇吃完变为最弱后新的最强蛇不敢吃它

第二条的理由是若该蛇不变为最弱，接下来本来比它弱的蛇要吃比它所吃蛇强的蛇，那只会变得比该蛇更弱

$1$、一开始，若满足第一、二条就一直决斗下去

$2$、到不满足时，先假设可以决斗，直到再遇到满足条件一、二时停下

此时正在判断的这次决斗可以进行

上一次决斗不会被发起，上上次则会被发起，上上上次不会

一直这样推下去，直到推回第一次不满足条件一、二的决斗，即可判断那次决斗是否会被发起

步骤$1$可以用两个队列维护

步骤$2$因为不满足条件一、二，每次最强蛇吃完都会变成最弱，那模拟决斗过程直接在原数组覆盖即可

代码巨丑

#include <bits/stdc++.h>

using namespace std;


inline int read() {
    int out = 0;
    bool flag = false;
    register char cc = getchar();
    while (cc < '0' || cc > '9') {
        if (cc == '-') flag = true;
        cc = getchar();
    }
    while (cc >= '0' && cc <= '9') {
        out = (out << 3) + (out << 1) + (cc ^ 48);
        cc = getchar();
    }
    return flag ? -out : out;
}

inline void write(int x) {
    if (x < 0) putchar('-'), x = -x;
    if (x == 0) putchar('0');
    else {
        int num = 0; char cc[20];
        while (x) cc[++num] = x % 10 + 48, x /= 10;
        while (num) putchar(cc[num--]);
    }
    putchar('
');
}



int T, n, k, l, r, ql, qr, siz;

struct snake {
    int w, id;
    bool operator < (const snake &g) const {
        return w == g.w ? id < g.id : w < g.w;
    }
    snake operator - (const snake &g) const {
        return snake{w - g.w, id};
    }
} st[1000010], a[1000010], q[1000010];


void solve() {
    l = 1, r = n, ql = 1, qr = 0, siz = n;
    for ( ; siz > 2; siz--) {
        snake Min = a[l], Max = a[r]; l++;
        if (ql <= qr && Max < q[ql]) Max = q[ql++];
        else r--;
        snake rest = Max - Min; Min = snake{0x3f3f3f3f, 0};
        if (l <= r && a[l] < Min) Min = a[l];
        if (ql <= qr && q[qr] < Min) Min = q[qr];
        if (rest < Min) {
            a[--l] = rest;
            break;
        }
        q[++qr] = rest;
    }
    if (siz == 2) puts("1");
    else {
        int opt = 1, ans = siz;
        while (true) {
            snake Min = a[l], Max = a[r]; l++;
            if (ql <= qr && Max < q[ql]) Max = q[ql++];
            else r--;
            siz--, opt ^= 1;
            if (siz == 2) {
                ans -= opt;
                break;
            }
            snake rest = Max - Min; Min = snake{0x3f3f3f3f, 0};
            if (l <= r && a[l] < Min) Min = a[l];
            if (ql <= qr && q[qr] < Min) Min = q[qr];
            if (rest < Min) a[--l] = rest;
            else {
                ans -= opt;
                break;
            }
        }
        write(ans);
    }
}

int main() {
    T = read() - 1;
    n = read();
    for (int i = 1; i <= n; i++) st[i] = a[i] = snake{read(), i};
    solve();
    while (T--) {
        k = read();
        for (int i = 1; i <= k; i++) {
            int x = read(), y = read();
            st[x] = snake{y, x};
        }
        for (int i = 1; i <= n; i++) a[i] = st[i];
        solve();
    }
    return 0;
}