链接
传送门
题意
给出\(n\)个数，\(n\)为偶数，每次操作可以选择一个数字加1或者减1，要求将这\(n\)个数分成两组，一组都是平方数，另一组都不是平方数。
思路
对于平方数，变为非平方数0需要2步，其他的需要1步。对于非平方数，可以预处理所有平方数，然后二分找到最接近的求解。
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
| #include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <vector>
typedef long long LL;
using namespace std;
const int maxn = 200010;
const int maxm = 31625;
int sqnum[maxm];
vector<int> sq, nsq;
int main() {
for (int i = 0; i < maxm; ++i) {
sqnum[i] = i * i;
}
int n;
scanf("%d", &n);
for (int i = 0, x; i < n; ++i) {
scanf("%d", &x);
int *it = lower_bound(sqnum, sqnum + maxm, x);
if (*it == x) {
sq.push_back(x == 0 ? 2 : 1);
} else {
nsq.push_back(min(*it - x, x - *(it - 1)));
}
}
n /= 2;
LL ans = 0;
if (sq.size() > nsq.size()) {
int dt = n - int(nsq.size());
sort(sq.begin(), sq.end());
for (int i = 0; i < dt; ++i) {
ans += sq[i];
}
} else {
int dt = n - int(sq.size());
sort(nsq.begin(), nsq.end());
for (int i = 0; i < dt; ++i) {
ans += nsq[i];
}
}
printf("%lld\n", ans);
return 0;
}
|