题目描述
难度分:$1500$
输入$T(\leq 2 \times 10^5)$表示$T$组数据。所有数据的$n$之和$\leq 2 \times 10^5$。
每组数据输入$n(1 \leq n \leq 2 \times 10^5)$和长为$n$的数组$a(1 \leq a[i] \leq 10^9)$。
每次操作,你可以选择一个大于$1$的$a[i]$,删除它,然后在它的位置上插入$x$和$a[i]-x$,其中$x$是一个小于$a[i]$ 的正整数。
例如$a=[1,10,9]$,把$10$分成$3$和$7$,数组变成$[1,3,7,9]$。
你需要把$a$变成非递减的,即$a[i] \leq a[i+1]$。
输出最少操作次数。
输入样例
4
3
1 3 2
4
1 2 3 4
3
3 2 1
7
1 4 4 3 5 7 6
输出样例
1
0
3
9
算法
贪心
因为并不确定第一个元素要不要拆,但是可以确定最后一个元素肯定是不拆更好,否则会增加前面元素的拆分操作,所以从后往前贪心。记上一个元素为$last$(初始情况下$last=a[n]$),当遍历到$a[i]$时如果发现$a[i] \gt last$,说明$a[i]$是必须要拆分的。为了让前面的数拆分次数尽可能少,最好的方式肯定是让$a[i]$的拆解更加平均,并且最大的值应该尽可能接近$last$,这样就能保证$a[i]$被拆解后的值尽量大,那么前面的数就有更大的可能性不拆。
$a[i]$被拆分之后的值必须在区间$[1,last]$之中,因此可以得到拆分数的个数$t=[\frac{a[i]+last-1}{last}]$,其中$[.]$为对$.$的下取整操作(此时可以让$[\frac{a[i]}{t}]$最接近$last$),拆分操作的次数为$t-1$,累加到答案上。拆分出来的最小数应该为$[\frac{a[i]}{t}]$,让它更新$last$,继续考前前一个数需不需要拆分即可。
复杂度分析
时间复杂度
算法整体就是倒序遍历了一遍数组,每次计算都是$O(1)$的,因此时间复杂度为$O(n)$。
空间复杂度
整个算法过程只使用了有限几个变量,空间复杂度为$O(1)$。
C++ 代码
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 200010;
int t, n, a[N];
void solve() {
int last = a[n];
long long ans = 0;
for(int i = n - 1; i >= 1; i--) {
if(a[i] <= last) {
last = a[i];
}else {
int t = (a[i] + last - 1) / last;
last = a[i] / t;
ans += t - 1;
}
}
printf("%lld\n", ans);
}
int main() {
scanf("%d", &t);
while(t--) {
scanf("%d", &n);
for(int i = 1; i <= n; i++) {
scanf("%d", &a[i]);
}
solve();
}
return 0;
}