给一个长为 \(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;
}