分析
h 指数等于使得研究员有至少 h 篇引用次数不少于 h 的论文的最大整数 h。
同时,他可以写综述引用 L 篇论文,并且只能引用每篇她的论文至多一次
因此,如果根据每篇论文的引用次数从大到小进行排序的话,对于前 h 篇论文,应该满足:
(1) 每一篇论文的引用次数都要 >= h - 1
(2) 且最多有 L 篇论文引用次数 = h - 1 (因为每篇论文最多只能在综述中引用一次)
对于每个 h ,都可以找到引用次数 >= h 的最后一篇论文的下标,设为 j。
我们可以发现:在引用次数递减的一个序列中,对于每个引用次数 h,随着 h 的增加 j 是逐渐减小的
因为 j 是引用次数 >= h 的最后一篇论文的下标,所以,下标在 j 后面、h 前面的论文引用次数均为 h - 1,这样的论文个数有 h - j 个
因此,对于 (1) 只需要索引为 h 处的论文引用次数 h - 1 即可,因为是递减的
对于 (2) : 如果索引为 h 处的论文引用次数 >= h 肯定是就可以的,如果索引为 h 处的论文引用次数为 h - 1 ,根据上文描述,这样的一共有 (h - j) 个,所以只需要 h - j <= l 即可
代码
#include<bits/stdc++.h>
using namespace std;
const int N = 1e5+10;
int w[N];
int n, l;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
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--;
if(w[i]>=i-1 && i-j<=l) res = i;
}
cout << res;
return 0;
}