解析
二分题直接理解后把模板背熟就行了,确实好用
代码逻辑也简单,直接上代码
Java
import java.util.Scanner;
public class Main{
static int N = 100010;
static int[] h = new int[N];
static int[] w = new int[N];
static int n,k;
public static void main(String[] args){
Scanner in = new Scanner(System.in);
n = in.nextInt();
k = in.nextInt();
for(int i = 0; i < n;i ++){ //初始化两个数组,分别存储长方形的两条边
h[i] = in.nextInt();
w[i] = in.nextInt();
}
int l = 1, r = 100000; //二分,注意r不能写成1e5,因为在java中1e5属于浮点数,就需要强制类型转化
while(l < r){
int mid = l + r + 1 >> 1; //因为使l = mid,所以应该向上取整+ 1
if(check(mid)) l = mid;
else r = mid - 1;
}
System.out.print(r);
}
private static boolean check(int mid ){ //检查res 是否大于等于 k,满足就向右边找,不满足就去左边找
int res = 0;
for(int i = 0; i < n; i ++){
res += (h[i]/mid) * (w[i]/mid);
}
return res >= k;
}
}