AcWing 3745. 牛的学术圈 I
原题链接
简单
作者:
渐修
,
2024-03-04 22:42:42
,
所有人可见
,
阅读 25
(二分+贪心)
/*
求最大的h指数,使至少h篇引用次数不少于h,则可知具有二段性,
n篇文章,h指数最大是h,最小为0
check函数:
首先从大到小排序每篇文章被引用的次数
若不能写一篇综述,要判断是否至少有h篇论文出现的次数大于h,只需判断前h篇(前面排序后它们出现的次数是前h大的)的次数是否大于h.
若能写综述
1:若前h篇文章有篇文章被引用的次数是小于h-1的,则二分的这个h肯定不满足(因为每篇文章最多只能被引用一次)
2:若被引用h-1次的文章出现的个数是小于l的,则二分的这个h也肯定不满足(因为最多引用l篇文章)
若以上都满足,则二分的这个h是满足条件的
*/
#include<iostream>
#include<algorithm>
using namespace std;
const int N=1e5+10;
int n,l;
int c[N];
bool check(int h)
{
int cnt[N]={0};//记录引用的次数对应文章出现的个数
for(int i=0;i<h;i++)
{
if(c[i]<h-1)
return false;
cnt[c[i]]++;
}
if(cnt[h-1]>l)
return false;
return true;
}
int main()
{
cin>>n>>l;
for(int i=0;i<n;i++)
cin>>c[i];
sort(c,c+n,greater<int>());
int l=0,r=n;
while(l<r)
{
int mid=l+r+1>>1;
if(check(mid))
l=mid;
else
r=mid-1;
}
cout<<l;
}