题目描述
牛的学术圈c语言小白
样例
//acwing牛的学术圈(双指针)
//N篇论文 ,第i篇Ci次引用
//h指数:至少有h篇引用次数不少于h的论文的最大整数h
//可引用L篇论文
//输出可以达到的最大h指数
#include <stdio.h>
#include <stdlib.h>
#define N 100010
int c[N];
int n,k;//n篇论文,k引用次数
int i,j;
int compare(const void *a,const void *b){
//转换数据类型并获取对应的值
return (*(int*)b-*(int*)a) ;
}
int main(){
//C语言中排序用qsort,需要先定义一个比较函数compare
scanf("%d%d",&n,&k);
for(i=1;i<=n;i++){
scanf("%d",&c[i]);//1 100 2 3
}
//qsort函数的参数依次是待排序数组的起始地址、
//元素个数、每个元素的大小(以字节为单位),以及用于比较元素的比较函数
qsort(c+1,n,sizeof(int),compare);
//数组从c[1]开始录入数据,因此这里的数组填的是c+1
int res=0;//记录答案
//双指针,i指向头,j指向尾
for(i=1,j=n;i<=n;i++){
//数组是逆着的 100 3 2 1
while( j && c[j]<i )j--; //找到第一个引用次数大于或等于i的论文位置
if( c[i]>=i-1 && i-j<=k )//i-j就是引用次数为i-1的论文个数,若小于引用次数则成立
res=i;
}
printf("%d",res);
return 0;
}
算法1
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
blablabla
算法2
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
blablabla