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 <iostream>
#include <algorithm>
#include <vector>

int main(){
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(0);
    int n;
    std::cin>>n;
    int t[n], cnt[n+1];
    for (int i=1; i<=n; ++i) cnt[i]=0;
    for (size_t i=0; i<n; ++i){
        std::cin>>t[i];
        ++cnt[t[i]];
    }
    std::vector<int> s;
    for (size_t i=1; i<=n; ++i)s.push_back(cnt[i]);
    std::sort(s.begin(),s.end());
    int i=0, j=s.size()-1, res=0;
    while (true){
        int ile=s[j];
        while (s[i]<ile){
            ile-=s[i];
            ++i;
        }
        s[i]-=(ile-1);
        if (i==j){
            std::cout<<res+1<<'\n';
            return 0;
        }
        --j;
        ++res;
    }
}