题解 CF1705B【Mark the Dust Sweeper】

Anguei

2022-07-18 14:53:51

Solution

## 题意 有一个数组 $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$ 是指删除了开头一段零之后的新数组信息。 ## 代码 ```cpp 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); } ```