牛的学术圈 (除了排序时间复杂度是On)

由于对计算机科学的热爱，以及有朝一日成为 「Bessie 博士」的诱惑，奶牛 Bessie 开始攻读计算机科学博士学位。

经过一段时间的学术研究，她已经发表了 N 篇论文，并且她的第 ii 篇论文得到了来自其他研究文献的 c~i~ 次引用。

Bessie 听说学术成就可以用 h 指数来衡量。

h 指数等于使得研究员有至少 h 篇引用次数不少于 h 的论文的最大整数 h。

例如，如果一名研究员有 4 篇论文，引用次数分别为 (1,100,2,3)，则 h 指数为 2，然而若引用次数为 (1,100,3,3) 则 h 指数将会是 3。

为了提升她的 h 指数，Bessie 计划写一篇综述，并引用一些她曾经写过的论文。

由于页数限制，她至多可以在这篇综述中引用 L 篇论文，并且她只能引用每篇她的论文至多一次。

请帮助 Bessie 求出在写完这篇综述后她可以达到的最大 h 指数。

注意 Bessie 的导师可能会告知她纯粹为了提升 h 指数而写综述存在违反学术道德的嫌疑；我们不建议其他学者模仿 Bessie 的行为。

输入格式

输入的第一行包含 N 和 L。

第二行包含 N 个空格分隔的整数 c~1~,…,c~N~。

输出格式

输出写完综述后 Bessie 可以达到的最大 h 指数。

数据范围

1≤N≤10^5^,
0≤c~i~≤10^5^,
0≤L≤10^5^

输入样例1：

4 0
1 100 2 3

输出样例1：

2

样例1解释

Bessie 不能引用任何她曾经写过的论文。上文中提到，(1,100,2,3) 的 h 指数为 2。

输入样例2：

4 1
1 100 2 3

输出样例2：

3

如果 Bessie 引用她的第三篇论文，引用数会变为 (1,100,3,3)。上文中提到，这一引用数的 h 指数为 3。

思路(给我狠狠的贪)

把这个题转化一下，题目描述，又是牛，又是论文，又是综述啥的烦死个人，转化后这个题思路就是，给你一个数组
a[N]，一共有N个数，用指数h，来描述数组，h代表至少有h个数大于等于h(最大的h),然后给我们一个数L,我们可以选择
最多L个数，使得每个数都加1,然后求出最大的指数h。

采用贪心策略，将数组按照降序进行排序，然后当a[i]>=i 且
i最大的时候，i就是我们当前数组的指数(这个比较简单不做证明，有问题评论区提问即可)。

首先我们要判断出，每个数最多只能加1，所以h指数最大只能是h+1,
(
证明：当前指数是h，a[h]>=h,a[h+1]<h+1,由于a[h+1]<h+1,所以a[h+1]最多只有变成h+1,不会变成h+2,更不会变更大，
在数组后面的数中，由于是逆序排列的，所以也小于等于h+1,更不可能变成h+2，由此可知，指数最大只能是h+1
)
所以我们现在要做的是选择部分数，然后让他们加1后使得a[h+1]==h+1,首先就是要选择a[h+1]这个点，在这里进行判断
，如果a[h+1]<h的话，就不可能变成h+1了(因为一个数最多加1)，所以最大指数就是h,如果a[h+1]==h的话，要找逆序排
列中在1~h+1，这个范围中有多少个点等于h(cnt个)，这些点都需要加1，因为这些点都需要大于等于h+1,所以，至少需要
cnt个点，当cnt<=L的时候满足条件，指数是h+1,否则是h

代码

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

const int N=100010;
int a[N];
int n,L;

bool cmp(int x,int y){
    return x>y;
}

int main(){
    cin>>n>>L;
    for(int i=1;i<=n;i++) cin>>a[i];

    sort(a+1,a+1+n,cmp);  //逆序

    int h=0;
    for(int i=1;i<=n;i++){
        if(a[i]>=i) h=i;  //找到我们的指数点
        else break;
    }
    if(a[h+1]<h){
        cout<<h<<endl;  //如果a[h+1]这个点小于h的话,则它就算加1也不会变成h+1,后面的数更不可能
        return 0;
    }
    int cnt=0;
    for(int i=1;i<=h+1;i++){
        if(a[i]==h) cnt++;   //计算出有多少个数是h
    }
    if(L>=cnt) cout<<h+1<<endl;   //满足条件则是h+1否则是h
    else cout<<h<<endl;
    return 0;

}