本文共 716 字，大约阅读时间需要 2 分钟。

题目大意：

刚开始有个数组，只有一个1，你可以进行两个操作：

1.把一个数复制到序列后面。 2.把一个数加上1。 你的任务是，通过上述操作，使所有数之和为一个给定值x,要求使操作次数尽可能小。

思考过程：

经过一段时间的摸索，不难发现，最优策略应该是：把1加到某个数，然后复制这个数，最后再把剩余的数加上去，直到得出结果。

经过摸♂索，我发现，要加到的这个数就是 根号x。 具体怎么证明可以看其它的大佬的博客，我的重点是细节处理 （其实是太菜了）

具体实现：

令s=sqrt(x)（向下取整）

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

代码：

#include
   
    #include
    
     #include
     
      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)，但是一直细节处理不好，归根到底，还是不知道怎么去分类讨论，所以这方面要多去考虑考虑。

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

转载地址：http://vuuci.baihongyu.com/