这是官方题解的 AI 中文翻译

我们将解法分为三个部分：

1. 找到操作次数的一个下界。
2. 通过提供一个使用该次数操作且最多运行 $N$ 次的解法，证明该下界是可达的。
3. 推导 $f(N)$，并说明如何修改上述解法以获得满分。

第一部分：下界

设 $a_i$ 表示我们攻击第 $i$ 个敌人的次数。我们必须满足 $0 \le a_i \le v_i$（第 $i$ 个类型 1 约束），以及 $a_{i-1} + a_i + a_{i+1} \ge v_i$（第 $i$ 个类型 2 约束），并希望最小化 $\sum a_i$。此外，$a_i$ 还需满足其他附加约束才能使解可行，但我们现在暂不考虑它们。

让我们从所有 $a_i$ 均为零开始，然后从左到右贪心地满足类型 2 的约束，通过选择某些 $a_i$ 进行增加。具体而言，为了满足第 $i$ 个类型 2 约束，我们应首先尽可能增加 $a_{i+1}$（这有助于满足尚未满足的最多类型 2 约束），仅在被迫时才增加 $a_i$。

这给出了 $\sum a_i$ 的一个下界，而在第二部分中，我们将证明该下界是可达的。

第二部分：一种构造方法

让我们为第一部分中每一个非零的 $a_i$ 输出一个恰好包含一次运行的构造。有多种不同的方法可以实现这一点，这里我们仅描述其中一种。

关键在于，对于满足 $a_i > 0$ 且 $a_{i-1} + a_i + a_{i+1} > v_i$ 的索引 $i$（称为“敏感索引”），我们在对 $i$ 执行操作时必须格外小心，因为绝对不允许将它们留到最后处理。事实上，我们可以证明不存在两个相邻的敏感索引，因此我们可以先对所有敏感索引执行操作，然后再处理其余索引。

该断言可通过分类讨论证明。对于每个索引 $i$，若 $a_{i+1}$ 增加以满足第 $i$ 个类型 2 约束，则在其位置标记一个 R；若 $a_i$ 增加以满足第 $i$ 个类型 2 约束（可能同时满足），则标记一个 S。我们可以注意到以下几点：

• 如果某个索引标记为 S，则其后续索引上不会标记任何字母。
• 由上述观察可知，不存在两个相邻索引同时标记为 S。
• 一个索引仅当其相邻索引标记为 S 时才可能是敏感的。
• 如果索引 $i$ 和 $i+3$ 均标记为 S，则 $a_{i+2} = 0$，因为 $i+1$ 处无 R 且 $i+2$ 处无 S，因此 $i+1$ 和 $i+2$ 不能同时为敏感索引。

由于类似推理，还存在其他可行的运行顺序。例如，从最大索引向最小索引执行操作，或根据需要交换某些不相交相邻对的顺序。

附注：若存在一个给定 $a$ 的构造，则必然存在一个使得每个非零 $a_i$ 恰好贡献一次运行的构造。这是因为，对于任意构造，若将每个索引 $i$ 上的操作移动至与索引 $i$ 的最后一次操作相邻的位置，构造依然有效。如果在原始构造中执行索引 $i$ 的最后一次操作之前 $v_i > 0$，那么在修改后的构造中这一性质同样成立。

第三部分：一个小的修改

我们断言，当 $N$ 为奇数时，$f(N) = N$。事实上，考虑 $v = [3, 1, 3, 1, \dots, 1, 3]$（大值与小值交替）。我们应当始终对所有小值执行操作，因为这是唯一能通过一次操作同时减少两个大值的方法。此外，我们还需要至少对所有大值执行一次操作，以将其减少至零。因此，第二部分中的构造方法对奇数 $N$ 已经适用。

当 $N$ 为偶数时，$f(N) = f(N-1) = N-1$，但在 $v_1 > v_2 < v_3 > v_4 < \dots > v_N$ 的情况下，我们的解法可能输出一个包含 $N$ 次运行的构造。在这种情况下，我们可以在构造解之前先反转输入数组，因为输入数组及其反转数组不可能同时满足该顺序。

#include <bits/stdc++.h>
using namespace std;

template <class T> using V = vector<T>;
#define all(x) begin(x), end(x)

using ll = long long;

int M;

pair<ll, vector<pair<int, ll>>> get_ops(const vector<ll> &v) {
    int N = size(v);

    // get op count
    vector<int> a(N);
    for (int i = 0; i < N; ++i) {  // satisfy i-th type 2 constraint by increasing a_{i+1} and a_i
        ll remaining = v.at(i) - a.at(i);
        if (i > 0) remaining -= a.at(i - 1);
        remaining = max(remaining, 0LL);
        if (i + 1 < N) {
            a.at(i + 1) = min(remaining, v.at(i + 1));
            remaining -= a.at(i + 1);
        }
        a.at(i) += remaining;
    }
    ll op_count = accumulate(begin(a), end(a), 0LL);

    // construction
    auto sensitive = [&](int i) {
        assert(0 <= i && i < N);
        return ((i == 0 ? 0 : a.at(i - 1)) + a.at(i) +
                    (i + 1 == N ? 0 : a.at(i + 1)) >
                v.at(i)) &&
               a.at(i);
    };
    vector<pair<int, ll>> runs;
    for (int i = 0; i < N; ++i)
        if (sensitive(i)) {
            if (i) assert(!sensitive(i - 1));
            // sanity check: no two consecutive sensitive indices
            runs.push_back({i, a.at(i)});
        }
    for (int i = 0; i < N; ++i)
        if (!sensitive(i) && a.at(i)) { runs.push_back({i, a.at(i)}); }
    return {op_count, runs};
}

void solve() {
    int N;
    cin >> N;
    vector<ll> v(N);
    for (auto &t : v) cin >> t;
    auto ans = get_ops(v);
    bool rev = false;
    if (N % 2 == 0 && size(ans.second) == N) {  // for M=2
        rev = true;
        reverse(all(v));
        ans = get_ops(v);
        assert(size(ans.second) < N);
    }
    const auto &[op_count, runs] = ans;
    cout << op_count << "\n";
    if (M) {
        cout << size(runs) << "\n";
        for (auto [i, r] : runs)
            cout << (rev ? N - i : i + 1) << " " << r << "\n";
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int T;
    cin >> T >> M;
    while (T--) solve();
}

翻译由 Qwen3-235B-A22B 完成