【題解】Codeforces 1490F. Equalize the Array

【題目敘述】https://codeforces.com/contest/1490/problem/F

#include <bits/stdc++.h>
using namespace std;
 
int t, n, a[200005], cnt[200005], ans, mn, now;
map <int, int> mp;
 
int main(){
    cin >> t;
    while (t--){
        cin >> n;
        mp.clear();
        for (int i = 1; i <= n; i++){
            cin >> a[i];
            mp[a[i]]++;
            cnt[i] = 0;
        }
        for (auto i:mp){
            cnt[i.second]++;
        }
        now = 0;
        ans = n;
        mn = n;
        for (int i = n; i >= 1; i--){
            ans += now;
            ans -= cnt[i]*i;
            mn = min(mn, ans);
            now += cnt[i];
        }
        cout << mn << "\n";
    }
}
分享本文 Share with friends