Fork me on GitHub

Codeforces 898E(思维)

Codeforces 898E
题意:给出一串数字,可以执行操作每次使一个数减一(数字大于0)或加一,问几次操作能使一半数为平方数,一半不是。
先记录数字中的平方数,如果正好一半,则不需要操作。
否则如果大于一半,则要枚举每个平方数改。注意到除了0要加2才能不是平方数,其他平方数加1都能不是平方数,所以优先修改非0平方数
如果小于一半,则要改最接近平方数的数。怎么找?可以考虑开方。$\sqrt a_i$如果小数部分大于0.5,则最接近$a_i$的数是$\sqrt a_i$的整数部分+1,否则是$\sqrt a_i$的整数部分-1.那么全部算出来排序优先改最接近平方数的数就可以了

Codeforces Submission

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
51
52
53
54
55
56
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
using namespace std;
const LL INF = 1000000005;
LL n, ai[200000 + 5];
LL cz[200000 + 5];
bool isPf(LL x) {
LL a = sqrt(x);
if (a * a == x) return true;
return false;
}
LL getCha(LL x) {
double a = sqrt((double)x) + 0.5;
LL b = (LL)a;
return abs(b * b - x);
}
void clean() {
}
void solve() {
clean();
LL ans = 0, taki = 0;
for (LL i = 1; i <= n; i++) {
scanf("%I64d", &ai[i]);
if (isPf(ai[i])) {
cz[i] = INF, taki++;
} else cz[i] = getCha(ai[i]);
}
LL z0 = 0, z1 = 0;
if (taki > n / 2) {
for (LL i = 1; i <= n; i++) {
if (cz[i] == INF) {
if (ai[i] == 0) z0++; else z1++;
}
}
if (z1 >= taki - n / 2) ans += taki - n / 2; else {
if (z1 < taki - n / 2) ans += z1, ans += (taki - n / 2 - z1) * 2;
}
printf("%I64d\n", ans);
} else {
if (taki == n / 2) {printf("%I64d\n", ans); return ;}
sort(cz + 1, cz + 1 + n);
for (LL i = 1; i <= n; i++) {
ans += cz[i], taki++;
if (taki == n / 2) break;
}
printf("%I64d\n", ans);
}
}
int main() {
scanf("%I64d", &n), solve();
return 0;
}

------ 本文结束 ------