codeforces : Increase and Copy 解题思路【数学】

题目大意：

刚开始有个数组，只有一个1，你可以进行两个操作：
1.把一个数复制到序列后面。
2.把一个数加上1。
你的任务是，通过上述操作，使所有数之和为一个给定值x,要求使操作次数尽可能小。
题目原地址https://codeforces.com/problemset/problem/1426/C

思考过程：

经过一段时间的摸索，不难发现，最优策略应该是：把1加到某个数，然后复制这个数，最后再把剩余的数加上去，直到得出结果。
经过摸♂索，我发现，要加到的这个数就是 根号x。
具体怎么证明可以看其它的大佬的博客，我的重点是细节处理
（其实是太菜了）

具体实现：

令s=sqrt(x)（向下取整）
首先要先加上s-1次
然后再加上s/(x-s)次
重点是后面：
s不一定每次都会被x整除
所以大多数情况下会省一个数，所以我们可以在把1往上加的时候，当它等于x%s的时候，复制一下，所以总次数会加一。加入能够整除，就不用加一了。

代码：

#include<cstdio>
#include<iostream>
#include<cmath>
using namespace std;

int n;

int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;++i){
        int x;scanf("%d",&x);
        int s=sqrt(x);
        printf("%d\n",s-1+x/(s-x)+(x%s!=0));
    }
    return 0;
}

一些思考：

比赛的时候知道要加到sqrt(x)，但是一直细节处理不好，归根到底，还是不知道怎么去分类讨论，所以这方面要多去考虑考虑。

觉得累了就来康康我老婆吧