Codeforces1426 C. Increase and Copy（思维，均值不等式）

题意：

你有一个序列，一开始只有一个元素1， 一次操作你可以选择一种进行： 1.将序列末尾的元素+1 2.设序列末尾的数为x，添加一个值为x的元素到序列的末尾，即复制。

给定n，问最少用多少次操作，能使得序列的总和>=n。

数据范围：n<=1e9

解法：

$假设存在操作序列p，其中操作1进行a次，操作2进行b次，$

$当每种操作的数量a和b固定时，将操作1全部放在最前面，一定是最优的。$

$那么我们只需要考虑一开始进行多少次操作1，后面全是操作2$

$---$

$假设操作1进行p次，那么操作2需要进行\lceil \frac{n-(p+1)}{p+1}\rceil =\lceil \frac{n}{p+1}\rceil -1次$

$那么总操作次数为p+\lceil \frac{n}{p+1}\rceil -1=[(p+1)+\lceil \frac{n}{p+1}\rceil ]-2$

$均值不等式:(p+1)+\frac{n}{p+1}>=2\ast sqrt(n)$

$那么当(p+1)取\lfloor sqrt(n)\rfloor 时,[(p+1)+\lceil \frac{n}{p+1}\rceil ]-2最小$

code：

#include<bits/stdc++.h> using namespace std; signed main(){ int T;cin>>T; while(T--){ int n;cin>>n; int p1=sqrt(n);//p+1取sqrt(n) int ans=p1+n/p1+(n%p1!=0)-2;//(n%p1!=0)是为了上取整 cout<<ans<<endl; } return 0; }

---