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
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 1;

int arr[maxn], number[maxn];

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

    int n; cin >> n;
    for(int i = 0; i < n; i++) cin >> arr[i];
    for(int i = 0; i < n; i++) number[arr[i]]++;

    sort(number, number + n, greater <int> ());

    int last = n - 1;
    bool flag = 0;
    for(int i = 0; i < n; i++){
        if(!number[i]) continue;
        int free = number[i] - 1;
        if(free == 0) continue;
        while(free--){
            while(!number[last]) last--;
            if(last == i) {flag = 1; break;}
            number[last]--; number[i]++;
        }
        if(flag) break;
    }
    int res = 0;
    for(int i = 0; i < n; i++) if(number[i]) res++;
    cout << res;
}