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

using namespace std;

const int MAXN = 5e5 + 7;
int t[MAXN];
int wystapienia[MAXN];

vector<int> vals;
map<int, int> mapa;

bool com(int a, int b)
{
    if(a >= b) return 1;
    else return 0;
}


/*
6 
1 1 2 2 3 3
*/
int main()
{
    int n, x = 0;
    cin >> n;
    for(int i = 0; i < n; i++)
    {
        cin >> t[i];
        mapa[t[i]]; // tworzenie komorki w mapie
    }

    for(auto it = mapa.begin(); it != mapa.end(); it++) it -> second = x++;
    for(int i = 0; i < n; i++) t[i] = mapa[t[i]];

    for(int i = 0; i < n; i++)
        wystapienia[t[i]]++;

    for(int i = 0; i < n; i++)
        if(wystapienia[i]) vals.push_back(wystapienia[i]);

    sort(vals.begin(), vals.end(), com);
    int odp = 0;
    int suma = 0; int ile_brakuje;

    while(vals.size())
    {
        if(vals.size() == 0) break;
        if(vals.size() == 1) {cout << ++odp << '\n'; return 0;}

        else if(suma + vals.back() < vals.front())
        {
            suma += vals.back(); vals.pop_back();
            if(vals.size() == 1) {odp++; break;}
        }
        else
        {
            ile_brakuje = vals.front() - (suma + 1);
            if(ile_brakuje == 0) {suma = 0; odp++; vals.erase(vals.begin());}
            else
            {
                int v = vals.back(); vals.pop_back();
                suma += ile_brakuje;
                vals.push_back(v - ile_brakuje);
                vals.erase(vals.begin());
                suma = 0;
                odp++;
            }
        }
    }
    cout << odp << '\n';
    return 0;
}