Untitled

 avatar
unknown
plain_text
8 months ago
1.2 kB
4
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;
            }
        }
        if(mp[0] < 2){
            cout << 0;
            return;
        }   
        int ans = mx * (mp[0]-1) , prev = mp[0]-1;
        for(int i = 0 ; i< mx ; i++){
            int mex = mx;
            int sum = 0;
            int j = i;
            while(j > 0){
                while((mex * (mp[j] - 1) + j )+ j * (mp[j-1] - 1) > mex * (mp[j-1] -1) && j > 0){
                    // cout << (mex * (mp[j] - 1) + j )+ j * (mp[j-1] - 1) <<' '<< mex * (mp[j-1] -1) + j + 1<< endl;
                    j--;
                }
                sum += mex * (mp[j]-1) + j;
                mex = j;
            }
            sum += mex *(mp[0]-1);
            // cout << sum << endl;
            ans = min (ans,sum);    
        }
        cout << ans;
    }   
Editor is loading...
Leave a Comment