思路
二分查找最大的满足条件的正方形的边长,
Java 代码
import java.util.Scanner;
public class Main {
static int n, k;
static int[] h, w;
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
n = sc.nextInt();
k = sc.nextInt();
h = new int[n];
w = new int[n];
for(int i = 0; i < n; i++) {
h[i] = sc.nextInt();
w[i] = sc.nextInt();
}
int l = 0, r = Integer.MAX_VALUE;
int res = 0;
while(l <= r) {
int mid = (l + r) / 2;
if(f(mid)) {
res = mid;
l = mid + 1;
}else {
r = mid - 1;
}
}
System.out.print(res);
}
public static boolean f(int mid) {
int t = 0;
for(int i = 0; i < n; i++) {
//t += (min[i] * min[i]) / (mid * mid);
//不能使用上面那种方法,例如 2*8的巧克力可以分成 2*2 四块
t += (h[i] / mid) * (w[i] / mid);
if(t >= k)
return true;
}
return false;
}
}