AcWing 3745. 牛的学术圈 I
原题链接
简单
作者:
无双飞怪
,
2024-04-17 21:28:16
,
所有人可见
,
阅读 1
思路 按照引用次数从大到小排序 然后找到大于等于i的数的下标
因为随着i增大i之前的数肯定逐渐不能满足条件 所以到了后面只须看以i为下标的数与真正的>=i的下标之间的差距是否小于等于l
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
const int N=1e5+10;
int n,l;
int a[N];
int main()
{
cin>>n>>l;
for(int i=1;i<=n;i++) scanf("%d",&a[i]);
sort(a+1,a+n+1,greater<int>());
int res=0;
for(int i=1,j=n;i<=n;i++)//i表示h指数
{
while(j&&a[j]<i) j--;//这里注意有--操作时一定要在while里写>=0
if(a[i]>=i-1&&i-j<=l) res=max(res,i);
}
cout<<res;
return 0;
}
另:“最大”想二分!!!
本题可以直接挨个统计>=h的数有多少个 ==h-1的数有多少个
至于h则可以用二分实现 二分出来
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
const int N=100010;
int n,L;
int w[N];
bool check(int mid)//二分h指数
{
int a=0,b=0;
for(int i=1;i<=n;i++)
if(w[i]>=mid) a++;
else if(w[i]==mid-1) b++;
return a+min(b,L)>=mid;
}
int main()
{
scanf("%d%d",&n,&l);
for(int i=1;i<=n;i++) scanf("%d",&w[i]);
int l=0,r=n;
while(l<r)
{
int mid=l+r+1>>1;
if(check(mid)) l=mid;
else r=mid-1;
}
cout<<r;
return 0;
}