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
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#include <set>

using namespace std;

const int MAXN = 5e5+7;

int iloscW[MAXN];

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int n, x;
    set<int> ciag;
    cin >> n;
    for(int i = 0; i < n; i++){
        cin >> x;
        ciag.insert(x);
        iloscW[x]++;
    }
    /*priority_queue<pair<int,int>> Q;
    priority_queue<pair<int,int>> Q2;
    for(int c : ciag){
        Q.push({iloscW[c], c});
        Q2.push({-1*iloscW[c], c});
    }
    int wyn = 0;
    while(!Q.empty()){
        pair<int,int> najczestszy = Q.top();
        Q.pop();
        if(iloscW[najczestszy.second] != 0){
            wyn++;
            //uzupelniamy iloscia-1 innych liczb
            cout << "lider " << najczestszy.second << "ile " << iloscW[najczestszy.second] << "\n";
            int do_uzupelnienia = iloscW[najczestszy.second]-1;
            iloscW[najczestszy.second] = 0;
            while(do_uzupelnienia > 0 && !Q2.empty()){
                pair<int,int> wyp = Q2.top();
                Q2.pop();
                if(iloscW[wyp.second] != 0){
                    cout << "-> uzupelniamy " << wyp.second << "\n";
                    int tmp = iloscW[wyp.second];
                    if(iloscW[wyp.second] <= do_uzupelnienia){
                        do_uzupelnienia -= iloscW[wyp.second];
                        iloscW[wyp.second] = 0;
                        cout << "nowe cnt " << wyp.second << " to " << iloscW[wyp.second] << "\n";
                    }else{
                        iloscW[wyp.second] -= do_uzupelnienia;
                        cout << "nowe cnt " << wyp.second << " to " << iloscW[wyp.second] << "\n";
                        do_uzupelnienia = 0;
                    }
                }
                if(iloscW[wyp.second] != 0){
                    Q2.push({-1*iloscW[wyp.second], wyp.second});
                }
            }
        }
    }*/
    set<pair<int,int>> S;
    int wyn = 0;
    for(int c : ciag){
        S.insert({iloscW[c], c});
    }
    while(!S.empty()){
        auto it = S.end();
        it--;
        int naj_ile = it->first;
        int naj_val = it->second;
        S.erase(it);
        if(iloscW[naj_val] != 0){
            wyn++;
            //cout << "lider " << naj_val << "ile " << iloscW[naj_val] << "\n";
            int do_uzupelnienia = iloscW[naj_val]-1;
            while(do_uzupelnienia > 0 && !S.empty()){
                auto it = S.begin();
                int uzu_val = it->second;
                S.erase(it);
                if(iloscW[uzu_val] <= do_uzupelnienia){
                    do_uzupelnienia -= iloscW[uzu_val];
                    iloscW[uzu_val] = 0;
                }else{
                    iloscW[uzu_val] -= do_uzupelnienia;
                    do_uzupelnienia = 0;
                }
                if(iloscW[uzu_val] > 0 ){
                    S.insert({iloscW[uzu_val], uzu_val});
                }  
            }
        }
    }
    cout << wyn << "\n";
    return 0;
}