Saltar al contenido

Tamaño máximo posible del subconjunto de acuerdo con las restricciones dadas

#include <bits/stdc++.h>

using namespace std;

 

bool is_possible(unordered_map<int, int>& mpp, int mid)

{

    bool flag1 = false;

    bool flag2 = false;

    bool flag = false;

    for (auto it : mpp) {

        if (it.second >= mid) {

            flag1 = true;

            if (it.second > mid)

                flag2 = true;

        }

    }

 

    int size = mpp.size() - 1;

    if (flag2)

        size += 1;

 

    return flag1 && size >= mid;

}

 

int maximum_size(vector<int>& arr, int n)

{

 

    

    

    unordered_map<int, int> mpp;

    for (auto it : arr) {

        mpp[it]++;

    }

 

    

    int low = 0;

    int high = n / 2;

 

    

    int ans = 0;

 

    while (low <= high) {

 

        

        int mid = (low + high) >> 1;

 

        

        

        

        

        if (is_possible(mpp, mid)) {

 

            ans = mid;

            low = mid + 1;

        }

 

        

        

        

        

        

        else {

            high = mid - 1;

        }

    }

 

    

    return ans;

}

 

int main()

{

    vector<int> arr = { 4, 2, 4, 1, 4, 3, 4 };

    int n = arr.size();

 

    

    cout << maximum_size(arr, n);

    return 0;

}