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
46
47
48
49
#include <cstdio>
#include <vector>
#include <algorithm>

int main() {
    std::vector<int> values;
    std::vector<int> sizes;
    int N, current, cnt, used, groups;

    scanf("%d", &N);
    for (int i=0; i<N; ++i) {
        int v;
        scanf("%d", &v);
        values.push_back(v);
    }

    std::sort(values.begin(), values.end());

    current = -1;
    cnt = 0;
    for (int v : values) {
        if (v == current) {
            cnt++;
        } else {
            if (cnt > 0) {
                sizes.push_back(cnt);
            }
            current = v;
            cnt = 1;
        }
    }
    sizes.push_back(cnt);

    std::sort(sizes.begin(), sizes.end(), std::greater<int>());

    used = 0;
    groups = 0;
    for (int s : sizes) {
        used += s + s-1;
        groups++;

        if (used >= N) {
            break;
        }
    }

    printf("%d\n", groups);
    return 0;
}