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
#include <bits/stdc++.h>
using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int n;
    cin>>n;
    vector<int> cnt(n+1,0);
    for (int i=0; i<n; i++) {
        int tmp;
        cin>>tmp;
        cnt[tmp]++;
    }
    sort(cnt.begin(),cnt.end());
    int s=0,e=n;
    while (cnt[s]==0) s++;
    int res=0;

    while (s<e) {
        res++;
        int left=cnt[e]-1;
        while (cnt[s]<=left && s<e) left-=cnt[s++];
        cnt[s]-=left;
        cnt[e--]=0;
    }

    if (cnt[s]!=0) res++;
    cout<<res<<'\n';

    return 0;
}