Codeforces Round 807 (Div. 2) B. Mark the Dust Sweeper

发布时间 2023-09-10 20:02:02作者: zsxuan

需要打扫 \(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;
}