引言

题目链接：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;
}