题意
如果一名研究员有 4篇论文,引用次数分别为 (1,100,2,3)则h指数为2然而若引用次数为 (1,100,3,3)则 h指数将会是 3。
对于(1,100,2,3);
当h为1时(1==1,100>1,2>1,3>1)所以1可以。
当h为2时(1<2,100>2,2==2,3>2)所以2可以。
当h为3时(1<3,100>3,2<3,3==3)仅有两种情况满足指数所以3不可以。
所以2是最大指数。
对于(1,100,3,3);
当h为1时(1==1,100>1,3>1,3>1)所以1可以。
当h为2时(1<2,100>2,3>2,3>2)所以2可以。
当h为3时(1<3,100>3,3>2,3==3)所以3可以。
所以3是最大指数。
二分
#include<iostream>
#include<algorithm>
using namespace std;
const int N=1e5+10;
int c[N];
int n,k;
//int an=0;
bool check(int mid)
{
int an=0;
int g=k;
for(int i=0;i<n;i++)
{
if(c[i]>=mid)an++;
else if(c[i]+1==mid&&g)g--,an++;//每篇最多被引用1次 +1==mid既符合题意
}
if(an>=mid)return true;
else return false;
}
int main()
{
cin >> n >> k;
int mid;
for(int i=0;i<n;i++)scanf("%d",&c[i]);
int l=0,r=1e5;
while(l<r)
{
mid=l+r+1>>1;
if(check(mid))l=mid;
else r=mid-1;
}
cout << l;
}
双指针
#include<iostream>
#include<algorithm>
using namespace std;
int q[100010];
int n,k;
int main()
{
int an=0;
cin >> n >> k;
for(int i=1;i<=n;i++)cin >> q[i];
sort(q+1,q+1+n,greater<int>());
for(int i=1,j=n;i<=n;i++)
{//在此i为指数
while(j&&q[j]<i)j--;//第一个大于i的q[];
if(q[i]>=i-1&&i-j<=k)//最小的q[]大于i-1,最大的位置数i减去最小的位置j:i-j小于可引用次数 即成立。
an=i;//更新答案。
}
cout << an;
}