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
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;

int occurences[500001];
vector<int> numbies;

int main() {
    int n;
    scanf("%d", &n);
    for (int i = 0; i < n; ++i){
        int a;
        scanf("%d", &a);
        occurences[a]++;
    }
    for (int i = 1; i <= n; ++i) {
        if (occurences[i] > 0) {
            numbies.push_back(occurences[i]);
        }
    }
    sort(numbies.begin(), numbies.end());
    int totalserved = 0;
    for (int i = numbies.size() - 1; i >= 0; --i) {
        totalserved += numbies[i] * 2 - 1;
        if (totalserved >= n) {
            printf("%d\n", numbies.size() - i);
            return 0;
        }
    }
    // unreachable
    return 0;
}