CF-1426C Increase and Copy 题解

题目大意

有个数组，最初只有一个1，你可以对他进行两种操作，复制其中的一个数，或者让其中一个数加一。问至少大于n需要的最小操作数。

解题思路

显然，先加在复制是最优解。

但是你不知道加到哪个数的时候是最优解。

而且他的n特别大，有1e9。

貌似我也没想到二分搜怎么做。

后面他们说了要打表找规律。

一看，规律就是0,1,2,2,3,3,4,4,4,5,5,5。

跟着规律输出就行了。

（以后看到这么大的数据，且算法复杂度不知道如何优化的题，要想到打表来做。。

完整代码

#include <iostream>
#include <algorithm>
using namespace std;
typedef long long ll;

ll num[70050];

int main() {
	int t; cin >> t;
	for (int i = 1; i <= 65000; i++)	num[i] = i * i + i;
	while (t--) {
		int n; cin >> n;
		int ans = 1e9;
		/*for (int i = 1; i <= n; i++) { 打表用
			int t = (i - 1);
			double tmp = 1.0*(n - i) / i;
			if ((int)tmp != tmp)	t++;
			t += (int)tmp;
			ans = min(ans, t);
		}*/
		int pos = lower_bound(num + 1, num + 65001, n) - num;
		n -= num[pos - 1];
		int i = pos;
		if (n <= pos)	ans = 2 * i - 2;
		else ans = 2 * i - 1;
		cout << ans << endl;
	}
}