题意
有一个数组 $a$,长度为 $n$。每次操作可以选两个坐标 $i < j$,且满足 $[i, j-1]$ 所有位置的元素都严格大于零,令 $a_i = a_i - 1$,$a_j = a_j + 1$。
问:至少多少次操作,可以使数组 $a$ 的前 $n-1$ 个元素都为零?
分析
如果这个数组,前 $x$ 个数字都是零,那么这部分就无需考虑。于是可以直接删除掉前面 $x$ 个零,同时更新 $n$ 的大小。
假如 $n=2$,那么最小的操作次数就是 $a_1$。
假如 $n=3$,那么最小操作次数就是 $a_1 + a_2$,即先用 $a_1$ 次操作,把第一个位置的数字全都挪给 $a_3$,再花 $a_2$ 次操作把第二个位置的数字也全都给 $a_3$。
但是如果这中间有一些为零的位置,就要先把这些位置填上一个数字。
因此,答案为 $\sum_{i=1}^{n-1}a_i + \operatorname{zeroCount}(1, n-1)$。此处的 $a$ 与 $n$ 是指删除了开头一段零之后的新数组信息。
代码
void solution() {
int n;
read(n);
std::vector<int> a(n + 1);
for (int i = 1; i <= n; ++i) read(a[i]);
ll sum = std::accumulate(a.begin() + 1, a.end() - 1, 0ll);
if (sum == 0) return print(0);
int start = 0;
for (int i = 1; i <= n - 1; ++i) {
if (a[i] > 0) {
start = i;
break;
}
}
int cnt = 0;
for (int i = start; i <= n - 1; ++i) if (a[i] == 0) ++cnt;
print(cnt + sum);
}