题解 CF1705B【Mark the Dust Sweeper】

2022-07-18 14:53:51


题意

有一个数组 $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);
}