思想:
- 将数组从大到小排序后,我们可以根据下标确定有多少篇引用量>=下标对应引用量: 如
100 3 2 1
即1篇>=100,2篇>=3,3篇>=2,4篇>=1
。 - 确定边界值(有可能优化h指数的地方):边界值即 下标>下标对应引用量的第一个位置。如
100 3 2 1 为i=3
和100 3 3 1 为i=4
。 - 其次,我们需要确定Bessie自己写的综述产生的引用量(仅能对多个+1),加在哪一部分利于提高h指数。
- 可以发现,提高h指数,实质是:将边界值+1以靠近下标
3篇>=2
,而将1往边界值后的小引用量加是没有作用的(小引用量和下标的差距一定>=2),所以如果有多余的L,应该往边界值前的大引用量+1。 - 重新排序后,寻找边界值,即为答案。
#include <bits/stdc++.h>
using namespace std;
const int N = 100010;
int c[N];
int main(){
int n,L,temp;
cin >> n >> L;
temp=n-1;
for(int i=1;i<=n;i++) cin >> c[i];
sort(c+1,c+n+1,greater<int>()); //从大到小排序:100 3 2 1
for(int i=n;i>=1;i--){ //寻找补1可以提高h指数的位置
if(c[i]>=i){ // i==3时,c[i]==2 此时c[i]+1,则h指数可以提高
temp=i;
break;
}
}
for(int i=temp+1;i>=1;i--){ //应当把1往大引用量加:即若有多余的L,应当:101 4 3 1。因为目标是通过分界处i和c[i]的调和,来使得h指数提高
if(L){
c[i]++;
L--;
}
}
sort(c+1,c+n+1,greater<int>()); //写完综述,论文的引用情况
for(int i=n;i>=1;i--){ // 100 3 3 1
//有i篇引用次数>=c[i]:有4篇引用次数>=1 有3篇引用次数>=3 有2篇引用次数>=3 有1篇引用次数>=100
if(c[i]>=i){ //100 3 2 1的情况:c[2]>=2时退出,即有2篇>=2但实际上有3篇>=2(至少h篇引用次数不少于h)
cout << i;
return 0;
}
}
cout << 0; //引用量全为0
return 0;
}
源码错了啊
5 0
0 0 0 0 0 输出null
应该特判最大值为0和l为0的情况
感谢指正,已修改特判
1 1
0
这组数据怎么过啊
这个测试点恰好验证了
L
如果有多余要往大引用量+1。你看代码第一个for循环出来,temp=1
,第二个for循环i从temp+1=2
开始到i=1
对c[i]
进行+1,所以c[1]
的位置上从0变成1了,也就是可以满足有1篇>=1,h指数就提高了1。感谢回复,第二个for循环从 i=temp+1=2 开始然后不就是c[2]+1了吗?然后l就消耗完了,没有半段范围问题吧,也可能是我太菜了,看不明白
c[2]的位置是有可能优化h指数的地方,所以c[2]+1,+1后排序完才是最后的引用量,所以本质上还是对可能优化h指数的地方+1导致了最后h指数的优化。
刚才没看清
L=1
hh把temp=n改成temp=n-1应该就行了
思路太像了,没想到L可以这样处理
太棒了,和我的思路一样, 看别人的题解用什么双指针的