AcWing 3745. 牛的学术圈 I
原题链接
简单
作者:
Jiezi
,
2024-03-05 19:26:05
,
所有人可见
,
阅读 15
二分
时间复杂度$O(nlogn)$
Java 代码
import java.io.*;
import java.util.Arrays;
public class Main {
static PrintWriter pw = new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out)));
static StreamTokenizer st = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
public static void main(String[] args) throws Exception {
// Code
// 读数据
int n = getInt();
int l = getInt();
int[] c = new int[n+1];
for (int i = 1; i <= n; i++) {
c[i] = getInt();
}
Arrays.sort(c); // 排序
/*
思路:若hi指数可以满足,那么1~hi也可以满足,采用二分答案
时间复杂度O(nlogn)
*/
int left = 0, r = n, ans = 0; // 最多为N
while (left <= r) {
int mid = (r - left) / 2 + left;
if (check(c, mid, l)) {
// 满足的话向右找最大的h
ans = mid;
left = mid + 1;
} else {
r = mid - 1;
}
}
pw.println(ans);
pw.flush();
}
/**
* 从大到小枚举h篇论文,看看能否达到h,达不到就去l里面借,最多借一次
* @param c 根据引用次数排好序的N篇论文
* @param h 满足的h指数
* @return 是否满足h
*/
public static boolean check(int[] c, int h, int l) {
int len = c.length;
if (h > len) return false;
for (int i = len - 1; i >= len - h; i--) {
if (c[i] < h) {
if (l > 0) {
if (c[i] + 1 < h) return false;
else l--;
}
else return false;
}
}
return true;
}
public static int getInt() throws Exception {
st.nextToken();
return (int) st.nval;
}
}