AcWing 3745. 牛的学术圈 I（每日一题）

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

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

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

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

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

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

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

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

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

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

输入格式

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

第二行包含 N个空格分隔的整数 c1,…,cN。

输出格式

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

数据范围

1≤N≤10^5 0≤ci≤10^5 0≤L≤10^5

输入样例1：

4 0
1 100 2 3

输出样例1：

2

样例1解释

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

输入样例2：

4 1
1 100 2 3

输出样例2：

3

样例2解释：

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

题目分析：

此题要求h指数，他可以引用自己的论文增加自己的h指数，最多引用一次，引用一篇则对应的一篇引用加1，所以分界线就在c[i]>=h与c[i]=h-1这里，其他的情况不用管。当c[i]>=h时，无论如何引用都已经大于h了，若想增加就在c[i]=h-1这里，引用一次对应加1，刚好到h，对于c[i]<h-1的无论如何加1都到不了h。我们可以二分查找h指数，当h符合条件，区间给到右区间，寻找有没有更大的选择。

代码实现

#include<iostream>
using namespace std;
int n,l;
int c[100005];
bool cheak(int mid){//判断此时mid是否符合h指数的条件
	int a=0;
	int b=0;
	for(int i=1;i<=n;i++){
		if(c[i]>=mid){//统计大于等于h的个数
			a++;
		}
		if(c[i]==mid-1){//统计刚好引用一次到h的个数
			b++;
		}
	}
	return a+min(b,l)>=mid;//a+min(b,l)为最终的h
}
int main(){
	cin>>n>>l;
	for(int i=1;i<=n;i++){
		cin>>c[i];
	}
	int l=0,r=n;
	while(l<r){
		int mid=l+r+1>>1;
		if(cheak(mid)){
			l=mid;
		}else{
			r=mid-1;
		}
	}
	cout<<r<<endl;
	return 0;
}

笔者水平有限，代码写的一般，若有错误，请大家指正，一起进步。