Submission

[PPPPPPPPPPPP]

Score: 100

User: Pera

Problemset: 01.H-index

Language: cpp

Time: 0.324 second

Submitted On: 2025-03-31 09:55:33

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL);
    int n; cin >> n;
    vector<long long> research(n);
    for (long long i = 0; i < n; ++i) cin >> research[i];

    vector<long long> counts(n + 1);
    for (long long i = 0; i < n; ++i) {
        counts[min(static_cast<long long>(n), research[i])]++;
    }

    vector<long long> at_least(n + 2);
    at_least[n+1] = 0;
    for (long long i = n; i >= 0; --i) {
        at_least[i] = at_least[i+1] + counts[i];
    }

    long long low = 0;
    long long high = n;
    long long h_index = 0;

    while (low <= high) {
        long long mid = (low + high) / 2;

        if (at_least[mid] >= mid) {
            h_index = mid;
            low = mid + 1;
        } else {
            high = mid - 1;
        }
    }

    cout << h_index << '\n';
}