AcWing 3745. 牛的学术圈 I
原题链接
简单
算法1
(双指针)
时间复杂度
参考文献
C++ 代码
#include<iostream>
using namespace std;
#include<algorithm>
int n,l;
int w[1000000];
int main(){
cin>>n>>l;
for(int i=1;i<=n;i++){
cin>>w[i];
}
sort(w+1,w+n+1,greater<int>());
int res=0;
for(int i=1,j=n;i<=n;i++){
while( j && w[j]<i) j--;
//至少h篇引用次数不少于h的论文的最大整数 h
/*直到满足条件w[j]>=i为止。i的值用于表示h值,
循环是找到h的最大值,其中至少有h篇论文的引用大于或等于h。*/
if(w[i]>=i-1&&i-j<=l)
//至少h篇引用次数不少于h的论文的最大整数 h
res=i;
}
cout<<res;
}
算法2
(二分)
时间复杂度
参考文献
C++ 代码
#include<iostream>
using namespace std;
#include<algorithm>
bool check(int mid){
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+mid(b,l)>=mid;
}
int n,l;
int w[1000000];
int main(){
cin>>n>>l;
for(int i=1;i<=n;i++){
cin>>w[i];
}
int l=0,r=n;
while(l<r){
int mid=(l+r+1)/2;
if(check(mid)) l=mid;
else r=mid-1;
}
cout<<l;
}