题意简述

有一个长度为 $n$ 的土豆焗菜被切成 $k$ 块，长度分别为 $a_i$。每次操作可将一块长度 $\ge 2$ 的块分成 $1$ 和 $a_i-1$，或将一块（任意长度）与一块长度为 $1$ 的块合并。求将所有块合并成完整一段所需的最少操作次数。

核心观察

• 长度为 $1$ 的块是合并的关键：任何长度大于 $1$ 的块只能通过与长度为 $1$ 的块合并来增长。
• 因此我们可以选择一块作为“主段”（不切割它），将其他所有块都变成 $1$ 并用主段逐一合并。
• 处理一块长度为 $L$ 的块（非主段）需要：
  • 切割 $L-1$ 次，将其变成 $L$ 个 $1$；
  • 合并 $L$ 次，将每个 $1$ 与主段合并。
• 总操作次数为 $(L-1) + L = 2L - 1$。特殊地，如果该块原长就是 $1$，只需合并 $1$ 次，即 $2\times1 - 1 = 1$。

公式推导

设我们选择长度为 $x$ 的块作为主段，其余块的总长度为 $n - x$，共有 $k-1$ 块。

总操作次数 = $\sum_{\text{其他块}} (2a_i - 1) = 2(n - x) - (k - 1) = 2n - 2x - k + 1$。

为了使操作次数最少，需要让 $x$ 尽可能大，即选择最长的一块作为主段。

答案为：

时间复杂度 $O(k)$ 每组，总 $O(\sum k) \le 2\times 10^5$。

参考代码

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

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

    int t;
    cin >> t;
    while (t--) {
        int n, k;
        cin >> n >> k;
        vector<int> a(k);
        int mx = 0;
        for (int i = 0; i < k; ++i) {
            cin >> a[i];
            mx = max(mx, a[i]);
        }
        ll ans = 2LL * n - 2LL * mx - k + 1;
        cout << ans << "\n";
    }
    return 0;
}