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

using namespace std;

int findMinSubsequences(const vector<pair<int, long long>>& sortedOccurrences) {
    vector<long long> cumulativeCapacity = {0};
    for (auto& occ : sortedOccurrences) {
        cumulativeCapacity.push_back(cumulativeCapacity.back() + (occ.second - 1));
    }

    vector<long long> cumulativeLengths(sortedOccurrences.size() + 1, 0);
    long long sum = 0;
    for (int i = sortedOccurrences.size() - 1; i >= 0; --i) {
        sum += sortedOccurrences[i].second;
        cumulativeLengths[i] = sum;
    }

    for (size_t i = 0; i < sortedOccurrences.size(); ++i) {
        if (cumulativeCapacity[i] >= cumulativeLengths[i + 1]) {
            return i + 1;
        }
    }

    return sortedOccurrences.size();
}

int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL); //zgodnie z radą
    int n;
    cin >> n;

    map<int, long long> occurrences;
    for (int i = 0, num; i < n; ++i) {
        cin >> num;
        occurrences[num]++;
    }

    vector<pair<int, long long>> sortedOccurrences(occurrences.begin(), occurrences.end());
    sort(sortedOccurrences.begin(), sortedOccurrences.end(), [](const pair<int, long long>& a, const pair<int, long long>& b) {
        return a.second > b.second;
    });

    int result = findMinSubsequences(sortedOccurrences);
    cout << result;

    return 0;
}