1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
#include <iostream>
#include <vector>
#include <map>

using namespace std;

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    int n; cin>>n;
    vector<int> nums(n+1);
    for(int i=0;i<n;++i){
        int x;
        cin>>x;
        nums[x]++;
    }

    map<pair<int,int>, bool> mp;
    for(int i=0;i<=n;++i){
        if(nums[i] > 1) mp[{nums[i],i}]=true;
    } 
    int sum{0};
    int groups{0};

    auto it = mp.rbegin();
    while(it != mp.rend()){
        auto [cnt, num] = it->first;
        
        int gsize = cnt+cnt-1;
        ++groups;
        n-=gsize;
        if(n<=0) break;
        it++;
    }

    if(n>=0) groups+=n;

    cout<<groups<<'\n';
}