题目描述

难度分:$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;
}