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

#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;
}