需要打扫 \(n\) 个房间，第 \(i\) 个房间有 \(a_i\) 的积灰。只能使用如下魔法打扫：
- 选择 \(i, j, (1 \leq i < j \leq n, \min_{k = i}^{j} a_i > 0)\) 。
- 执行 \(a_i = a_i - 1, a_j = a_j + 1\) 。
需要将 \(1 \sim n - 1\) 号房间的积灰全部清空，最少使用多少次魔法。
观察一：显然最后所有的积灰会被移到第 \(n\) 个房间。
- 从贡献角度考虑， \(n\) 号房间必须消耗 \(\sum_{i = 1}^{n-1} a_i\) 次魔法。
观察二：从第一个有积灰的房间开始，到 \(n - 1\) 号房间，所有积灰为 \(0\) 的房间会作为一次中转。
- 从贡献角度考虑：从第一个有积灰的房间往右，一个积灰为 \(0\) 的房间必须且仅会消耗一次魔法获得 \(1\) 的积灰。
观察三：其他房间不会消耗贡献。
令 \([1, n - 1]\) 中第一个没有积灰的房间坐标为 \(l\) ，\(l = 0\) 表示不存在。
for (int i = 1; i < n; i++) if (l == 0 && a[i] == 0 && a[i - 1] > 0) l = i;
答案为 \([l \neq 0]\sum_{i = l}^{n-1}[a_i=0] + \sum_{i=1}^{n-1}a_i\) 。
view
#include <bits/stdc++.h>
void solve() {
int n; std::cin >> n;
std::vector<int> a(n+1);
int l = 0; long long sum = 0;
for (int i = 1; i <= n; i++) std::cin >> a[i];
for (int i = 1; i < n; i++) if (l == 0 && a[i] == 0 && a[i - 1] > 0) l = i;
for (int i = 1; i < n; i++) sum += a[i];
std::cout << sum + (l != 0) * std::count(a.begin() + l, a.begin() + n, 0) << '\n';
}
signed main() {
int _ = 1; std::cin >> _;
while (_--) solve();
return 0;
}