细胞分裂
简化题意：将数组中任何一个元素替换为任意两个和为该元素的数字。将数组变成元素按非递减顺序排列的数组，所需的最少操作次数。
思路概述：这道题我认为就是一个贪心加数学的题目，因为题目要求所有操作过后，除最后一个数外，每个数都不大于后一个数。因此一个数越大，留给前面的数的空间才越多。所以得到贪心结论：最后一个数不拆。
那样根据我们得出的第一个结论，从后往前推，那么不妨设当前这个数字是 x ，它的后一位是 y 。那么久就只有这三种情况。
-
若 x \leq y ，根据贪心，我们不应该拆分了，已经满足了。
-
若 x>y ，我们需要拆分 x 使得拆分后的最大值不超过 y ，而且根据贪心，拆分后的最小值要尽可能的大，那我们设 (k-1) \times y<x \leq k \times y （也就是说 k=\left \lceil \frac{x}{y} \right \rceil ），但是我们根据抽屉原理不难得出 x 至少要被拆分成 k 份，不然最大值一定会超过 y 。但是因为拆的次数越少，而且拆的平均才可能让这个值尽可能地大。因此我们对 x 进行 (k-1) 次拆分把它变成 k 个数。其中的最小值呢，就是 k=\left \lfloor \frac{x}{k} \right \rfloor 。
-
若 x=y ，什么也不用动，最好的情况。
#include<bits/stdc++.h>
using namespace std;
int n;
int a[100005];
int main()
{cin>>n;for(int i=1;i<=n;i++){cin>>a[i];}long long ans=0;int last=a[n];//维护反向枚举中遇到的最小值(包括拆分之后的)for(int i=n-1;i>0;i--){if(a[i]>last){int cnt=ceil((double)a[i]/last);//一共要分成几个数ans+=cnt-1;//统计拆分次数last=a[i]/cnt;//切分后的最小值为a[i]/cnt(无论是否能整除)}else if(a[i]<last)//不需要拆分维护最小值{last=a[i];}//剩下的哪一类不用管。}cout<<ans<<endl;return 0;
}