当前位置: 代码迷 >> 综合 >> codeforces : Increase and Copy 解题思路【数学】
  详细解决方案

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

热度:62   发布时间:2024-01-21 21:15:33.0

题目大意:

刚开始有个数组,只有一个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),但是一直细节处理不好,归根到底,还是不知道怎么去分类讨论,所以这方面要多去考虑考虑。

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

在这里插入图片描述

  相关解决方案