牛的学术圈_(双指针）

原题链接：3745. 牛的学术圈 I - AcWing题库

题意：在一堆数里，找到至少 大于等于 h 的 h个数，在一定的加一操作内，试求最大的h

思路

找到大于等于h的，h个数 从大到小排序，遍历到 a[i] < i

当有加一操作时，简单的查找行不通，需要遍历找每个可能 h 因为加一之后会破坏排序 存在某种情况我没发现但是会导致直接找出错

要找的数，变为：大于等于h-1的数，并且其中值h-1的数不超过给定的操作数。

如果枚举h ，再对h-1枚举，时间复杂度太高

发现当 h 变大，大于等于 h-1 的数的索引变小（因为大到小排序） 单调变化，可以双指针

实现

要找到大于等于 h 最后一个数，同时找到大于等于 h-1 的最后一个数，两者一减就是h-1的数的范围

#include <iostream>
#include <algorithm>
 
using namespace std;
 
const int N = 1e5 + 10;
 
int a[N];
 
//试试双指针
int main()
{
    int n, L;
    cin >> n >> L;
    
    for(int i = 1; i <= n; i ++)
    {
        cin >> a[i];
    }
    
    sort(a + 1, a + n + 1, greater<int>());
    
    //双指针
    int ans = 0;
    //双指针还原查找过程
    for(int i = 1, j = n; i <= n; i ++)
    {
        //j是大于等于i的最后一个数
        while(j && a[j] < i) j --;
        //a[i]大于等于i-1的最后一个数，那么两者相减就是h-1的数
        if(a[i] >= i - 1 && i - j <= L)
            ans = i;
    }
    cout << ans << endl;
    
    return 0;
}