Link

Question

给出一个长度为 \(n\) 的序列 \(a\) ，我们可以做一种操作使得 \(a\) 非降，操作是：

对于一个 \(a_i\) 选择一个整数 \(0 \le x \le a_i\) ，用两个数 \(x,(a_i-x)\) 来替换 \(a_i\)。

求最小操作次数。

Solution

考虑哪些数是需要操作的，如果 \(a_i\) 比后面一个数大，那么这个数肯定需要进行操作来减小 \(a_i\)。

再思考对于一个数 \(a_i\) 需要怎么操作，定义后面一个数在操作后的最小值是 \(last\) ，那么 \(a_i\) 在操作后的最大值肯定不大于 \(last\) ，贪心的想法，操作次数越少越好，操作次数就是 \(K=\lceil a_i/last \rceil-1\)，操作后，我们肯定希望 \(a_i\) 生成的数的最小值越大越好，再贪心的想法，最大的最小值就是 \(\lfloor a_i/(K+1) \rfloor\) 。

那么从后往前处理，记录每个 \(a_i\) 操作的次数以及更新 \(last\)。

Code

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int maxn=2e5+5;
inline int read(){
    int ret=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-f;ch=getchar();}
    while(ch<='9'&&ch>='0')ret=ret*10+ch-'0',ch=getchar();
    return ret*f;
}
int a[maxn];
signed main(){
    // freopen("B.in","r",stdin);
    int T=read();
    while(T--){
        int N=read();
        for(int i=1;i<=N;i++) a[i]=read();
        int num=1,lst=a[N];
        for(int i=N-1;i;i--){
            if(a[i]<=lst){num+=1;lst=a[i];continue;}
            int K=a[i]/lst+(a[i]%lst!=0);
            lst=a[i]/K;
            num+=K;
        }
        printf("%lld\n",num-N);
    }
    return 0;
}