Increase and Copy - 每天一把CF -20201020

每天一把CF : 2020-10-20

题目

原题链接:https://codeforces.com/problemset/problem/1426/C

思路

题目大意：给定一个数组a，开始数组a中只有一个数1，有两个操作，1.选择数组中一个数+1。 2.选择数组中一个数，将这个数复制一份再放进数组中. 给定一个数n，问使数组a的和大于等于n的最小操作数是多少。

思路：首先我们先思考一下，肯定是把一个数加到足够大之后，再去复制这个数就好了。不然先复制再一个个去加，浪费的步数会非常多。

然后这个问题就变成了x*y==n 求x+y的最小值得问题了（有点不准确，但大致是这样，不一定能相等），然后再用我们的小学数学想一想，肯定是x==y的时候x+y值最小，所以最后就是sqrt（n）*sqrt（n）然后在去更正一下其中的一些误差。所以最后答案是

ans1 = tp * 2 - 2 + (n - tp * tp) / tp + (n % tp ? 1 : 0);//从x*x出发 tp++;//从(x+1)*(x+1)出发 ans2 = tp * 2 - 2; ll t = tp * tp; while (t >= n) { t -= tp; ans2--; } ans1 = min(ans1, ++ans2);

代码实现

#include <iostream> #include <cstring> #include <algorithm> #include <map> #include <cmath> using namespace std; #define ll long long const int MAX = 1e5 + 5; ll t, n, ans1, ans2; int main() { cin >> t; while (t--) { cin >> n; ll tp = sqrt(n); ans1 = tp * 2 - 2 + (n - tp * tp) / tp + (n % tp ? 1 : 0);//从x*x出发 tp++;//从(x+1)*(x+1)出发 ans2 = tp * 2 - 2; ll t = tp * tp; while (t >= n) { t -= tp; ans2--; } ans1 = min(ans1, ++ans2); //cout << "->"; cout << ans1 << endl; } return 0; }