引言
题目链接：https://codeforces.com/contest/1898/problem/B
思路
首先根据题目要求，要求操作后的数组是非递减数组，所以只能从后向前遍历数组进行操作
对于当前需要进行操作的 \(a_i\) 来说一定是使其分解出来的数尽可能相等的做法是最优方案
那么对于 \(a_i,a_{i+1}\) 来说，假设 \(a_i > a_{i + 1}\)
我们要对 \(a_i\) 进行操作，则需要将其分解成 \(cnt = \lceil \frac{a_i}{a_{i + 1}} \rceil\) 个数才能保证对于每个分解出的数尽可能相等且都小于 \(a_{i + 1}\)
将其分解成 cnt - 1 块后，最小的数放在最左边
该数为 \(\lfloor \frac{a_i}{cnt} \rfloor\)
例：
\(a_i=10，a_{i+1}=4\)一种方案是将 \(a_i\) 分解为 2,4,4
这显然不是最优方案
其最优方案一定是将 \(a_i\) 分解为 3,3,4
代码
#include <bits/stdc++.h>
#define ll long long
#define N 200100
ll a[N];
void solve() {
int n;
std::cin >> n;
for (int i = 1 ; i <= n ; i ++ ) {
std::cin >> a[i];
}
ll res = 0;
ll now = a[n];
for (int i = n - 1 ; i >= 1 ; i -- ) {
if(a[i] <= now) {
now = a[i];
}
else {
ll cnt = (a[i] + now - 1) / now;
res += cnt - 1;
now = a[i] / cnt;
}
}
std::cout << res << "\n";
}
int main() {
int t;
std::cin >> t;
while(t -- ) {
solve();
}
return 0;
}