题解

问题分析

题目描述了蛇之间的决斗规则：每轮实力最强的蛇可选择吃掉实力最弱的蛇（自身体力值减去弱蛇体力值）或结束决斗。蛇的目标是在不被吃掉的前提下尽可能多吃其他蛇，且所有蛇都足够聪明。需计算决斗结束后存活的蛇的数量，且支持多组数据（每组数据可能修改部分蛇的体力值）。

关键观察：

1. 蛇的实力由体力值和编号决定（体力值大的更强；体力值相等时，编号大的更强）。
2. 初始及修改后的数据均保证体力值按非降顺序排列（a_1 ≤ a_2 ≤ ... ≤ a_n），简化了强弱判断。
3. 最强蛇是否吃最弱蛇，取决于吃后是否仍能保证自身不被后续轮次的最强蛇吃掉，且能继续吃更多蛇。

核心思路

采用递归模拟决斗过程，结合贪心策略判断每一步是否应吃掉最弱蛇：

1. 标识当前范围：用x（当前最强蛇的右边界）、y（当前最弱蛇的左边界）表示未被吃掉的原始蛇范围，用l、r表示因“吃蛇”产生的新蛇（存储在数组d中）的范围。
2. 确定当前最强和最弱蛇：
   • 最强蛇（p）：从原始蛇的右边界x和新蛇的右边界r中选择实力更强的。
   • 最弱蛇（q）：从原始蛇的左边界y和新蛇的左边界l中选择实力更弱的。
3. 判断是否吃蛇：吃掉最弱蛇后，新的最强蛇体力值为a[p] - a[q]。若该值仍能保证其在后续轮次中是最强的（或至少不被吃掉），则继续吃；否则停止。
4. 递归处理后续轮次：每吃掉一条蛇后，更新边界并递归判断下一轮是否继续，直至无法再吃或选择停止。

代码解析

#include <cstdio>
#include <algorithm>
using namespace std;

int T, n;
int b[2000007];  // 存储当前蛇的体力值（支持修改）
int a[2000007];  // 临时数组，用于模拟决斗过程（避免修改原始数据）
int d[2000007];  // 存储吃蛇后产生的新蛇的编号

// 获取当前最强蛇（p）：比较原始蛇右边界x和新蛇右边界r
int get_zq(int x, int y, int l, int r) {
    if (x < y) return d[l];  // 原始蛇已吃完，返回新蛇
    if (l > r) return x;     // 新蛇已吃完，返回原始蛇右边界
    // 比较原始蛇x和新蛇r的实力（体力值或编号）
    if (a[x] > a[d[r]]) return x;
    return d[r];
}

// 获取当前最弱蛇（q）：比较原始蛇左边界y和新蛇左边界l
int get_zr(int x, int y, int l, int r) {
    if (x < y) return d[r];  // 原始蛇已吃完，返回新蛇
    if (l > r) return y;     // 新蛇已吃完，返回原始蛇左边界
    // 比较原始蛇y和新蛇l的实力（体力值或编号）
    if (a[y] <= a[d[l]]) return y;
    return d[l];
}

// 递归处理吃蛇后的后续轮次
int dg_c(int x, int y, int l, int r) {
    // 剩余2条蛇时，无法再吃（吃后只剩1条，决斗结束）
    if (x - y + 1 + r - l + 1 == 2) return 1;

    // 确定当前最强蛇p并更新其边界
    int p = get_zq(x, y, l, r);
    if (p == x && x >= y) x--;  // p是原始蛇，右边界左移
    else l++;                   // p是新蛇，左边界右移

    // 确定当前最弱蛇q并更新其边界
    int q = get_zr(x, y, l, r);
    if (q == y && x >= y) y++;  // q是原始蛇，左边界右移
    else r--;                   // q是新蛇，右边界左移

    // 判断吃蛇后是否仍能保持优势
    int ss = get_zr(x, y, l, r);  // 下一轮的最弱蛇
    if (a[p] - a[q] > a[ss] || (a[p] - a[q] == a[ss] && p > ss)) {
        // 吃后仍占优，继续吃
        return 1;
    } else {
        // 吃后可能被吃，停止并返回已吃数量
        a[p] -= a[q];
        d[++r] = p;
        return 1 - dg_c(x, y, l, r);
    }
}

// 主递归函数：模拟整个决斗过程
int dg() {
    // 复制当前体力值到临时数组a（避免修改原始数据b）
    for (int i = 1; i <= n; i++) a[i] = b[i];
    
    int l = 1, r = 0;  // 新蛇数组d的左右边界（初始为空）
    int x = n, y = 1;  // 原始蛇的左右边界（初始为全部蛇）

    // 最多吃n-2条蛇（最后至少剩1条）
    for (int i = 1; i <= n - 2; i++) {
        // 确定当前最强蛇p并更新边界
        int p = get_zq(x, y, l, r);
        if (p == x && x >= y) x--;
        else l++;

        // 确定当前最弱蛇q并更新边界
        int q = get_zr(x, y, l, r);
        if (q == y && x >= y) y++;
        else r--;

        // 判断是否继续吃蛇
        int ss = get_zr(x, y, l, r);  // 下一轮的最弱蛇
        if (a[p] - a[q] > a[ss] || (a[p] - a[q] == a[ss] && p > ss)) {
            // 吃后仍占优，更新新蛇数组
            a[p] -= a[q];
            d[++r] = p;
        } else {
            // 吃后可能被吃，停止并计算存活数量
            a[p] -= a[q];
            d[++r] = p;
            return n - i + dg_c(x, y, l, r);
        }
    }

    // 若吃完n-2条蛇，只剩1条存活
    return 1;
}

int main() {
    scanf("%d", &T);
    scanf("%d", &n);
    // 读取初始蛇的体力值
    for (int i = 1; i <= n; i++) scanf("%d", &b[i]);
    // 计算第一组数据的结果
    printf("%d\n", dg());

    // 处理后续T-1组数据（含修改操作）
    for (int yggbr = 1; yggbr < T; yggbr++) {
        int k;
        scanf("%d", &k);
        // 执行k次修改（覆盖更新）
        for (int i = 1; i <= k; i++) {
            int x, z;
            scanf("%d%d", &x, &z);
            b[x] = z;
        }
        // 计算当前组数据的结果
        printf("%d\n", dg());
    }

    return 0;
}

复杂度分析

• 时间复杂度：每组数据的递归深度为O(n)，每次递归涉及常数次边界更新和比较，因此单组数据复杂度为O(n)。对于T组数据，总复杂度为O(T×n + ∑k)（∑k为所有修改操作的总数），可满足n ≤ 1e6、T ≤ 10的规模。
• 空间复杂度：O(n)，用于存储蛇的体力值和临时数组。

核心优势

1. 利用数据的非降序特性，简化了最强/最弱蛇的查找（仅需关注边界）。
2. 通过递归模拟决斗过程，结合贪心判断是否继续吃蛇，确保每一步都是最优选择。
3. 临时数组a的使用避免了修改原始数据，支持多组数据的连续处理。

该算法高效处理了蛇的决斗逻辑，通过精准的边界管理和递归判断，正确计算了存活蛇的数量。