acwing -- 3745. 牛的学术圈 I-526互联

h指数问题，当看到题目要求最大，最小的字眼是，可以想到二分，dp，枚举。

本题采用二分答案，对h指数进行二分。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>

using namespace std;

const int N = 1e5 + 10;

int n, m;
int arr[N];

bool check(int x) {
    int res = 0;
    for(int i = 1; i <= n; i ++ ) {
        if(arr[i] >= x) res ++ ;
    }
    return res >= x;
}

int main() {
    cin >> n >> m;
    int l = 1e8, r = -1;
    for(int i = 1; i <= n; i ++ ) {
        cin >> arr[i];
        l = min(l, arr[i]);
        r = max(r, arr[i]);
    }
    
    while(l + 1 < r) {
        int mid = l + r >> 1;
        if(check(mid)) l = mid;
        else r = mid;
    }
    
    sort(arr + 1, arr + n + 1);
    
    for(int i = n; i > 0; i -- ) {
        if(m == 0) break;
        if(arr[i] <= l) arr[i] ++ , m -- ;
    }
    
    l = -1, r = 1e8;
    while(l + 1 < r) {
        int mid = l + r >> 1;
        if(check(mid)) l = mid;
        else r = mid;
    }
    
    cout << l << endl;
    
    return 0;
}

学术