题解：CF1490F Equalize the Array

yueyixuan1 · 2026-05-10 13:58:49 · 题解

思路

首先看到题目想到计数。令 mp_i 表示 i 出现的次数。

首先令 id 表示出现最多的一个数。

考虑暴力，会超时。

我们发现每次暴力有一段部分其实可以预处理，这就用到前缀和。

假设我们要求每个数出现 p 次：

• 出现数量小于 p，删掉 p 个数。
• 出现数量不小于 p，删掉它出现的次数减去 p 个数。

我们枚举的时候，要想看有多少个小于，就用二分即可。

核心代码

inline void calc(VI &x){
    vector<int> r;
    r.pb(0);
    for(auto y : x){
        r.pb(y);
    }
    x=r;
}

inline int f(const VI &res, int x){
    int L=0,R=SZ(res);
    while(L+1<R){
        int M=(L+R)>>1;
        if (res[M]>=x){
            R=M;
        } else{
            L=M;
        }
    }
    return (res[L]>=x)?L:R;
}

inline void solve(){
    n=read();
    for(int i=1;i<=n;a[i++]=read());
    for(int i=1;i<=n;i++){
        mp[a[i]]++;
    }
    VI res;
    for(auto [x,y] : mp){
        res.pb(y);
    }
    stable_sort(all(res));
    int l=SZ(res);
    calc(res);
    for(int i=1;i<=l;i++){
        s[i]=s[i-1]+res[i];
    }
    int ans=11451419198107891;
    for(int i=1;i<=n;i++){
        int id=f(res ,i);
        ans=min(ans, s[id-1]+(s[l]-s[id-1]-(l-id+1)*i));
    }
    writeln(ans);
    mp.clear();
}