[AdditionalFile5632.zip](file://AdditionalFile5632.zip?type=additional_file)

#5632. 「USACO 2026 Third Platinum」Blast Damage

标签: 传统 | 时间限制: 2000 ms | 内存限制: 256 MiB |

题目描述

题目译自 USACO 2026 Third Contest, Platinum Problem 2. Blast Damage

Bessie 正在玩一款电子游戏。在游戏中，她需要击败一排 $N$ 个敌人，他们的初始血量分别为 $v_1, \dots, v_N$ $(1 \le N \le 2 \cdot 10^5, 0 \le v_i \le 10^9)$。在一次攻击中，她可以执行以下步骤：

• 选择一个仍然存活的敌人 $i$（即 $v_i > 0$）。
• 对第 $i$ 个敌人以及与其相邻且仍然存活的敌人各造成 $1$ 点伤害。具体来说，对于每个 $j \in [\max(i-1, 1), \min(i+1, N)]$，如果 $v_j > 0$，则将 $v_j$ 减 $1$。

请帮助 Bessie 确定击败所有敌人（即让所有 $v_i$ 降为 $0$）所需的最少攻击次数。

此外，你还会得到一个参数 $M$ $(0 \le M \le 2)$。如果 $M > 0$，请输出一个以较少连续打击次数实现最少攻击总数的构造方案。一次连续打击是指连续攻击同一个敌人。

设你的构造方案中连续打击的次数为 $R$。你的构造方案应符合以下格式：首先在单独的一行输出 $R$，随后输出 $R$ 行，每行包含两个整数 $i$ 和 $r$ $(1 \le i \le N, 0 \le r \le 10^9)$，表示 Bessie 连续攻击第 $i$ 个敌人 $r$ 次。

根据 $M$ 的值，$R$ 必须满足以下约束之一：

• $M=1$：$R \le 2N$（可以证明总能找到满足此条件的构造方案）。
• $M=2$：$R \le f(N)$，其中 $f(N)$ 是在所有长度为 $N$ 的序列中，达到最少攻击总数所需的最小连续打击次数的最大值。

输入格式

每个输入包含 $T$ $(1 \le T \le 10^5)$ 个独立的测试用例。第一行包含 $T$ 和 $M$。

每个测试用例的格式如下：

• 第一行包含 $N$。
• 第二行包含 $v_1, \dots, v_N$。

保证所有测试用例的 $N$ 之和不超过 $10^6$。

输出格式

对于每个测试用例，第一行输出最少攻击次数。

如果 $M > 0$，则按照上述要求额外输出 $R+1$ 行。你可以输出任何一个满足条件的构造方案。

样例 1

输入

2 0
1
10
3
6 1 7

输出

10
12

对于第二个测试用例，你可以先对中间的敌人进行一次攻击。然后在此之后的任何顺序中，对第一个敌人进行五次攻击，并对最后一个敌人进行六次攻击。

样例 2

输入

2 1
1
10
3
6 1 7

输出

10
2
1 0
1 10
12
4
2 1
1 5
3 2
3 4

此输出是正确的，因为对于测试用例 $1$，$R=2 \le 2$；对于测试用例 $2$，$R=4 \le 6$。

样例 3

输入

2 2
1
10
3
6 1 7

输出

10
1
1 10
12
3
2 1
3 6
1 5

此输出是正确的，因为对于测试用例 $1$，$R=1 \le f(1)$；对于测试用例 $2$，$R=3 \le f(3)$。

数据范围与提示

• 测试点 4-7：$M=0$
• 测试点 8-11：$M=1$
• 测试点 12-13：$M=2$

供题：Benjamin Qi