Codeforces Round #674 C Increase and Copy【数学】

数学】"/>

Codeforces Round #674 C Increase and Copy【数学】

题目链接

题目描述：

题解：

it is pretty intuitive that we firstly need to do all increaments and only then copy numbers. You could notice that the answer does not exceed n 1 / 2 n^{1/2} n1/2 so we can iterate from 1 to ⌊ n 1 / 2 ⌋ \lfloor n^{1/2} \rfloor ⌊n1/2⌋ and fix number we will copy. Let it be x. Then we need x - 1 moves to obtain it and also need ⌈ n − x x ⌉ \lceil \frac{n-x}{x} \rceil ⌈xn−x​⌉ moves to get the enough number of copies. So we can update the answer with this number of moves.

二分答案：

我比赛的时候用的二分答案做的，首先令 x 为increments 的次数，y 为 copy 的次数，n 为总 moves 的次数，有 n = x + y。设 w 为经过 x 次 increment 和 y 次 copy 后得到的值，即 w = (1 + x) * y，经过与 n = x + y 联立，求导并代入，最终得到 ( n + 1 2 ) 2 (\frac{n+1}{2})^2 (2n+1​)2 为 n 次操作的最大值，然后进行二分答案即可，最终得到的结果要减 1。

Tips：

If you want to calculate ⌈ X Y ⌉ \lceil \frac{X}{Y} \rceil ⌈YX​⌉ then you do this: (X + Y - 1) / Y or (X - 1) / Y + 1 .
this works because division is rounded down if you cast the result to int

做法1(93ms)：

#include <iostream>
#include <vector>
#include <queue>
#include <stack>
#include <set>
#include <map>
//#include <unordered_set>
//#include <unordered_map>
#include <deque>
#include <list>
#include <iomanip>
#include <algorithm>
#include <fstream>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <cstdlib>
//#pragma GCC optimize(2)
using namespace std;
typedef long long ll;
//cout << fixed << setprecision(2);
//cout << setw(2);
const int N = 2e5 + 6, M = 1e9 + 7;int main() {//freopen("/Users/xumingfei/Desktop/ACM/test.txt", "r", stdin);ios::sync_with_stdio(false);cin.tie(0), cout.tie(0);int t;cin >> t;while (t--) {int n;cin >> n;int ans = 1e9;for (int i = 1; i * i <= n; i++) {ans = min(ans, i - 1 + (n - i - 1) / i + 1);}cout << ans << '\n';}return 0;
}

二分答案(15ms)：

#include <iostream>
#include <vector>
#include <queue>
#include <stack>
#include <set>
#include <map>
//#include <unordered_set>
//#include <unordered_map>
#include <deque>
#include <list>
#include <iomanip>
#include <algorithm>
#include <fstream>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <cstdlib>
//#pragma GCC optimize(2)
using namespace std;
typedef long long ll;
//cout << fixed << setprecision(2);
//cout << setw(2);
const int N = 2e5 + 6, M = 1e9 + 7;int main() {//freopen("/Users/xumingfei/Desktop/ACM/test.txt", "r", stdin);ios::sync_with_stdio(false);cin.tie(0), cout.tie(0);int t;cin >> t;while (t--) {int n;cin >> n;int l = 0, r = 1e9;while (l + 1 < r) {double mid = (l + r) >> 1;if (pow((mid + 1) / 2, 2) >= n) {r = mid;} else {l = mid;}}if (pow((1.0 * l + 1) / 2, 2) >= n) {cout << l - 1 << '\n';} else {cout << r - 1 << '\n';}}return 0;
}