CF1898B Milena and Admirer - CF题解 | 123hh2 = Keep moving forward

# 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;
	}