题目描述
由于对计算机科学的热爱,以及有朝一日成为 「Bessie 博士」的诱惑,奶牛 Bessie 开始攻读计算机科学博士学位。
经过一段时间的学术研究,她已经发表了 N
篇论文,并且她的第 i
篇论文得到了来自其他研究文献的 ci
次引用。
Bessie 听说学术成就可以用 h
指数来衡量。
h
指数等于使得研究员有至少 h
篇引用次数不少于 h
的论文的最大整数 h
。
例如,如果一名研究员有 4
篇论文,引用次数分别为 (1,100,2,3)
,则 h
指数为 2
,然而若引用次数为 (1,100,3,3)
则 h
指数将会是 3
。
为了提升她的 h
指数,Bessie 计划写一篇综述,并引用一些她曾经写过的论文。
由于页数限制,她至多可以在这篇综述中引用 L
篇论文,并且她只能引用每篇她的论文至多一次。
请帮助 Bessie 求出在写完这篇综述后她可以达到的最大 h
指数。
注意 Bessie 的导师可能会告知她纯粹为了提升 h
指数而写综述存在违反学术道德的嫌疑;我们不建议其他学者模仿 Bessie 的行为。
算法1
(二分+前缀和) $O(nlogn)$
h成立需要两个条件:1.当前最小值>=h-1
2.要用到的等于h-1的数不超过l个
我们可以发现,在[1,n]区间中,可以找到一个最大的h,使得所有小于等于它的数都能满足条件,大于它的数都不满足条件,我们可以用二分找到这个h。
计算要用到的等于h-1的数时,可以用前缀和先预处理出每个值对应的个数。
时间复杂度
参考文献
C++ 代码
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int N=1e5+10;
int n,l,c[N],cnt[N];
bool cmp(int x,int y)
{
return x>y;
}
bool check(int mid)
{
if(c[mid]>=mid-1&&mid-cnt[N-6]+cnt[mid-1]<=l) return true;
return false;
}
int main()
{
scanf("%d%d",&n,&l);
for(int i=1;i<=n;i++)
{
scanf("%d",&c[i]);
cnt[c[i]]++;
}
for(int i=0;i<=N-5;i++) cnt[i]+=cnt[i-1];
sort(c+1,c+1+n,cmp);
int l=0,r=c[1]+1;
while(l<r)
{
int mid=(l+r+1)>>1;
if(check(mid)) l=mid;
else r=mid-1;
}
printf("%d",r);
}
算法2
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码