先看题目描述： 小埋从他的一个神秘仰慕者那里得到了一个长度为 n 的整数数组 a1,a2,…,an。小埋认为让数组不递减就能辨认出这位神秘的仰慕者。 小埋可以使用下面的操作使数组不递减：
-
选择数组 a 中的元素a i 和一个整数 x,使得 1<=x<ai 。两个元素 x 和ai−x 替换 ai，新的元素x和ai−x 将依次放入数组 a 。
-
更具体的说，假设操作前的数组是 1,2,…,a1,a2,…,ai,…,ak 是数组 a。操作之后，它就等于1,2,…,ai−1,x,ai-x,ai+1,…,an。注意，每次操作后，a 的长度都会增加 1
再看样例：
4
3
1 3 2
4
1 2 3 4
3
3 2 1
7
1 4 4 3 5 7 6
我们一组一组看：
3
1 3 2
把3分成两份 ：1和2
变成：1,1,2,2
再来看下一个样例
4
1 2 3 4
无论是拿一个，都不用变
3
3 2 1
先把2 分成两份：1，1
现在是 3，1，1，1（这里注意，是只有两次分割）
再把3分成3分：1 1 1
最后就是1，1，1，1，1，1
欧耶，又水完一段
最后也是最难的一段：
7
1 4 4 3 5 7 6
从后往前看，7比6大分成两份足以：3和4
这是为了保持3和4的良好性质，这里保留成3 4 6
接着5比3大，也是平分，2 和3。 现在是2 3 3 4 6
接着3比2大，平分。现在是1 2 2 3 3 4 6
接下来的两个4都是要分成4份，也就是分三次，1 1 1 1 1 1 1 1 1 1 2 3 3 4 6
一共有1+1+1+3+3=9次
这里你发现我一直在讲分成几个几次
但是这里的都是均分，为什么，因为一下三点
- 不能浪费太多，因为你每填一个数字都是后面的上限，不然下一个是100，但是你这一个是1
- 不能把小的太小，因为后面的就会要减少很多。不然就可以把1000分成1和999，这样分的次数一定多许多
- x加大时ai-x一定减少。但是要同时满足的话只有均分时才行。
那么我们从找到x变成找到分成几份。
这里的代码运用了和线性斐波纳吉差不多的思路，核心代码如下：
for(int i = n-1;i >= 1;i--){
int x = a[i + 1] / c;
c = ( a[ i ] + x - 1 ) / x;
c = max( c , 1ll );
res += c - 1;
}
温馨提示：进度条已过半，请放心食用。
前话：c是上一个分割的份数
我们一条一条来看， for()是为了倒序检查，因为最后一个就是最高的值，不可能超过他。
接下来的x是用来存储a i+1 / c的。
接下来就是确定这次的*a i*分成几份
c = max( c , 1ll );
这个就是防止出现x分成0.114514份的。
（网友：
）
接下来就是统计，很简单吧。
接下来就是写其他的初始化和输入了
初始化：
#include <bits/stdc++.h>
using namespace std;
int t,n,a[200010];
const int mod=1e9+7;
输入：
cin>>n;
for(int i=1;i<=n;i++){
cin>>a[i];
}
接下来就没有了，这题就是基本的思维题，代码3分钟，思考两年半。
总代码
#include <bits/stdc++.h>
using namespace std;
int t,n,a[200010];
const int moduled=1e9+7;
int main()
{
while(cin>>t){
while(t--){
cin>>n;
memset(a,0x3f,sizeof(a));
for(int i=1;i<=n;i++){
cin>>a[i];
}
long long res=0,c=1;
for(int i=n-1;i>=1;i--){
int x=a[i+1]/c;
c=(a[i]+x-1)/x;
c=max(c,1ll);
res+=c-1;
}
cout<<res<<" ";
}}
return 0;
}
拜拜 
