CF1898B Milena and Admirer

CF1898B Milena and Admirer

题目链接

题目大意

给出一个长度为 $n(1 \leq n \leq 2*10^5)$ 的数组 $a_i(1 \leq a_i \leq 10^9)$ ，你可以将数组中任意一个数 $a_i$ 分成两个数 $x,a_i-x$ ，求使该数组非严格递增的最小操作数

思路

容易发现，无论如何操作，数组中的数都会小于等于数组中最后一个数并大于等于第一个数

所以可以贪心的从后往前遍历数组，碰到 $a{i-1} > a_i$ 的情况就分裂 $a{i-1}$ ，这时候为了确保后续操作数更少，我们需要让分裂出的最小数尽可能大，所以不妨考虑将 $a{i-1}$ 尽可能平均分成 $x$ 份，此时分裂出的数保证最大数 $\frac{a{i-1}+a{i-1}\%x}{x} \leq a_i$ ，最小数 $\frac{a{i-1}-a{i-1}\%x}{x} \geq a{i-2}$ 即可

代码

#include<bits/stdc++.h>
#define int long long
#define in inline
#define ri register
#define _123hh2 0
using namespace std;
in int read()
{
    int x=0,f=1;char ch=getchar();while(ch>'9'||ch<'0') {if(ch=='-') f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9') {x=(x<<3)+(x<<1)+(ch^48);ch=getchar();}return x*f;
}
in void write(int x) {if(x<0) {x=-x;putchar('-');}if(x>9) write(x/10);putchar(x%10+'0');}
const int maxn=2e5+1;
int awa[maxn];
signed main()
{
    int  t=read();
    while(t-->0)
    {
        int n=read(),now,cnt=0;
        for(int i=1;i<=n;i++) awa[i]=read();
        now=awa[n];
        for(int i=n-1;i>=1;i--)
        {
            if(awa[i]>now)
            {
                int x=awa[i]/now-1;
                if(awa[i]%now) x++;
                cnt+=x;
                now=awa[i]/(x+1);
            }
            else now=awa[i];
        }
        write(cnt),puts("");
    }
    return _123hh2;
}