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
41
42
43
44
45
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

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

    int input_size; cin >> input_size;

    vector<int> exist(input_size + 1);

    int temp;

    for(int i = 0; i < input_size; i ++){
        cin >> temp;
        exist[temp] ++;
    }

    sort(exist.begin(), exist.end());

    int left = 0, right = input_size, number_of_groups = 0, actual_size;

    while(left <= right){
        actual_size = exist[right];
        number_of_groups ++;
        
        while(left <= right){
            if(exist[left] + actual_size < exist[right] * 2){
                actual_size += exist[left];
                left ++;
            } else {
                exist[left] = exist[left] - (exist[right] * 2 - actual_size - 1);
                break;
            }
        }
        right --;
    }

    cout << number_of_groups << '\n';

    return 0;
}