526互联

Codeforces Round 787 (Div. 3) B. Make It Increasing

发布时间 2023-09-13 18:40:43作者: zsxuan

给一个长为 \(n\) 的数组 \(a_1, a_2, \cdots, a_n \quad (0 \leq a_i \leq 10^9)\) 。可以执行以下操作任意次：

  • 选择任意一个 \(a_i\) 并且执行 \(a_i = \lfloor \frac{a_i}{2} \rfloor\) 。

输出最小操作次数，使得数组所有元素变为严格递增。

观察：数组一些位置变小，将数组变为严格递增。右端点的 \(a_n\) 不变最优。

  • 当 \(n = 1\) ，数组严格递增。
  • 当 \(n \geq 2\) ，从 \(n - 1\) 开始往前扫，保证每个 \(a_i < a_{i + 1}\) 。当且仅当 \(a_{i + 1} == 0\) ，无法通过操作使得 \(a_i < a_{i + 1}\) 。（由于 \(n = 1\) 时被另外判断可以保证 \(i + 1\) 位置合法）
  • 复杂度保证：任意 \(a_i\) 最多执行 \(\log_2 {10^9} = 30\) 次操作，时间复杂度为 \(O(n)\) 。
view 
#include <bits/stdc++.h>
void solve() {
	int n; std::cin >> n;
	std::vector<int> a(n+1);
	for (int i = 1; i <= n; i++) std::cin >> a[i];
	if (n == 1) std::cout << 0 << '\n';
	else {
		int cnt = 0;
		for (int i = n - 1; i; --i) {
			if (a[i + 1] == 0) {
				std::cout << -1 << '\n';
				return;
			}
			while (a[i] && a[i] >= a[i + 1]) {
				a[i] /= 2; cnt++;
			}
		}
		std::cout << cnt << '\n';
	}
}
signed main() {
	int _ = 1; std::cin >> _;
	while (_--) solve();
	return 0;
}