Acwing 春季每日一题 3745. 牛的学术圈 I

Acwing 春季每日一题 3745. 牛的学术圈 I

思路：

首先说明一下什么是h指数，就是对于给定的一个论文引用数，如果在这一堆引用数中，有h个数的大小大于等于h，剩余的 l - h个数都严格小于h，就得到了h指数，h指数可能不唯一。

这道题就是在不满足的数上可以操作一次 + 1，这样我们可以枚举h的长度，同时如果我们对数组进行降序排序，然后在h这么长下，找到第一个大于等于h的数，然后在这个数的后面一直到第h个数，如果每个数都满足大于等于h - 1,而且这个长度还小于给定的L，那么我们就可以去更新这个区间，同时我们可以发现，如果要求所有的数都是大于等于h - 1，只需要满足最后一个数a[i] 是大于等于 i - 1的就可以了，如果这个数不满足，那么 + 1是不会满足h指数的条件的，同时可以发现，对于每次h的增长，第一个大于等于h的数一定是在后移的，所以我们可以使用双指针算法。

代码：

#include<iostream>
#include<algorithm>
using namespace std;

const int N = 1e5+10;
int a[N];
int n,L;

int main(){
    cin>>n>>L;
    for(int i = 1; i <= n; i++) cin>>a[i];
    
    sort(a + 1,a + n + 1,greater<int>());
    int res = 0;
    //找到第一个大于h的数 然后看 这个数到h这一段的个数是不是小于L 如果是就更新res
    //同时判断a[i - 1] 这个数是不是小于等于 h - 1的
    for(int i = 1,j = n;i <= n;i++){
        while(j && a[j] < i) j--;
        if(i - j <= L && a[i] >= i - 1) res = i;
        
    }
    cout<<res;
    return 0;
}