题目描述
1.双指针写法
2.二分写法
双指针写法
import java.util.*;
/*
先把引用次数的数组逆序排序,
双指针写法:j指的位置就是值为h,i和j-1指的位置就是值为h-1,并且i - j <= L, i不断变大,符合条件res = i,最后h=res
*/
public class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int N = 100010;
Integer[] w = new Integer[N];
int n = scanner.nextInt();
int L = scanner.nextInt();
for (int i = 1; i <= n; i++) {
w[i] = scanner.nextInt();
}
//使用逆序排序 注意数组要变成Integer类型 如果直接正序排不用边Integer
Arrays.sort(w, 1, n+1, Comparator.reverseOrder());
int res = 0;
for (int i = 1, j = n; i <= n; i++) {
while (j > 0 && w[j] < i) j--;
if (w[i] >= i - 1 && i - j <= L) {
res = i;
}
}
System.out.println(res);
}
}
二分写法
import java.util.*;
public class Main {
/*
二分思想:统计值大于等于h的个数,统计值等于h-1的个数,两个数字相加看看个数是否等于h,不等就继续二分
*/
static final int N = 100010;
static int[] w = new int[N];
static int n,L;
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
n = scanner.nextInt();
L = scanner.nextInt();
for (int i = 1; i <= n; i++) {
w[i] = scanner.nextInt();
}
int l = 0, r = n;
while (l < r)
{
int mid = l + r + 1 >> 1;
if (check(mid)) l = mid;
else r = mid - 1;
}
System.out.println(r);
}
static boolean check(int mid)
{
int a = 0, b = 0;
for (int i = 1; i <= n; i ++ )
if (w[i] >= mid) a ++ ;
else if (w[i] == mid - 1) b ++ ;
//b是不能超过最多可引用文章数量
return a + Math.min(b, L) >= mid;
}
}