Codeforces Round #451 (Div. 2) E - Squares and not squares 打表+暴力

xiaoxiao2021-02-28  6

#include<iostream> #include<algorithm> #include<cstdio> #include<cstdlib> #include<cstring> #include<string> #include<cmath> #include<set> #include<queue> #include<stack> #include<map> #define PI acos(-1.0) #define in freopen("in.txt", "r", stdin) #define out freopen("out.txt", "w", stdout) #define kuaidian ios::sync_with_stdio(0); using namespace std; typedef long long ll; typedef unsigned long long ull; const int maxn = 2e5+7; const ll maxd = 2e9; const ll mod = 1e9 + 7; const int INF = 0x7f7f7f7f; ll n, cnt = 0; ll a[maxn], s[maxn], vis[maxn]; vector<ll> vec; void init() { memset(vis, 0, sizeof vis); cnt = 0; for(ll i = 0; i*i <= maxd; ++i) { s[cnt++] = i*i; } } int main() { kuaidian; init(); cin >> n; int num = 0, numm = 0; for(int i = 0; i < n; ++i) { cin >> a[i]; if( (ll)sqrt(a[i])*(int)sqrt(a[i]) == a[i] ) vis[i] = 1, num++; if(a[i] == 0) numm++; } if(num == n/2) return puts("0")*0; else if(num > n/2) { int t = num - n/2; ll ans = 0; if(num - numm < t) { ans += (num - numm); t -= (num - numm); ans += 2*t; } else ans = t; cout << ans << endl; } else { int t = n/2 - num; ll ans = 0; for(int i = 0; i < n; ++i) { if(vis[i]) continue; int pos = lower_bound(s, s+cnt, a[i]) - s; vec.push_back( min(s[pos]-a[i], a[i]-s[pos-1]) ); } sort(vec.begin(), vec.end()); for(int i = 0; i < t; ++i) { ans += vec[i]; } cout << ans << endl; } return 0; }