AcWing 1227. 分巧克力 - JAVA - 二分
原题链接
简单
作者:
acw_weian
,
2021-01-15 16:05:29
,
所有人可见
,
阅读 562
import java.io.*;
class Main{
static BufferedReader read = new BufferedReader(new InputStreamReader(System.in));
static BufferedWriter log = new BufferedWriter(new OutputStreamWriter(System.out));
public static void main(String[] args ) throws Exception{
String[] ss = read.readLine().split(" ");
int n = Integer.valueOf(ss[0]), k = Integer.valueOf(ss[1]);
int[][] a = new int[n][2];
for(int i = 0; i < n; i++){
ss = read.readLine().split(" ");
int h = Integer.valueOf(ss[0]), w = Integer.valueOf(ss[1]);
a[i][0] = h; a[i][1] = w;
}
int l = 1, r = 100000;
while(l < r){
int mid = l + r + 1 >> 1;
if(check(a, mid, k)) l = mid;
else r = mid - 1;
}
System.out.println(l);
}
public static boolean check(int[][] a, int size, int k){
int ans = 0;
for(int i = 0; i < a.length; i++){
int h = a[i][0], w = a[i][1];
for(int row = 0; row + size <= h; row += size){
for(int col = 0; col + size <= w; col += size){
ans++;
}
}
}
return ans >= k;
}
}