Untitled

 avatar
unknown
plain_text
5 months ago
1.1 kB
2
Indexable
void Gojo(){
    int n;cin>>n;
    vector<int> v;
    map<int,int> mp;
    For(n){
        int x;cin>>x;
        if(mp[x] == 0)v.push_back(x);
        mp[x]++;
    }
    sort(v.begin(),v.end());
    int mex= 0 , mx = v.size();
    for(int i = 0; i <  v.size() ; i++){
        // cout << v[i] <<' ';
        if(i != v[i]){
            mx = i;
            break;
        }
    }
    v.clear(); int mn = mp[0];
    for(int i = 1; i < mx ; i++){
        if(mp[i] <= mn)v.push_back(i);
        mn = min(mn,mp[i]);
    }
    if(mp[0] < 2){
        cout << 0;
        return;
    }   
    int ans = mx * (mp[0]-1) , prev = mp[0]-1;
    for(int i = 0 ; i< v.size(); i++){
        int mex = mx;
        int sum = 0;
        int j = v[i];
        while(j > 0){
            while((mex * (mp[v[j]] - 1) + v[j] )+ v[j] * (mp[v[j-1]] - 1) > mex * (mp[v[j-1]] -1) && j > 0){
                j--;
            }
            sum += mex * (mp[v[j]]-1) + v[j];
            mex = v[j];
        }
        sum += mex *(mp[0]-1);
        // cout << sum << endl;
        ans = min (ans,sum);    
    }
    cout << ans;
}
Editor is loading...
Leave a Comment