题目大意:
刚开始有个数组,只有一个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),但是一直细节处理不好,归根到底,还是不知道怎么去分类讨论,所以这方面要多去考虑考虑。
觉得累了就来康康我老婆吧