AcWing 1227. 分巧克力 Java 整数二分
原题链接
简单
作者:
天乔巴夏丶
,
2021-01-16 14:22:38
,
所有人可见
,
阅读 387
import java.util.*;
class Main{
static int n, k, max;
static int[][] nums;
public static void main(String[] args){
Scanner sc = new Scanner(System.in);
n = sc.nextInt();
k = sc.nextInt();
nums = new int[n][2];
for(int i = 0; i < n; i ++){
nums[i][0] = sc.nextInt();
nums[i][1] = sc.nextInt();
max = Math.max(max, Math.max(nums[i][0], nums[i][1]));
}
int l = 0, r = max;
while(l < r){
int mid = l + r + 1 >>> 1;
if(check(mid)) l = mid;
else r = mid - 1;
}
System.out.println(l);
}
static boolean check(int mid){
int res = 0;
for(int[] num : nums){
// 计算取mid时,目前是否已经符合要求
res += (num[0] / mid) * (num[1] / mid);
if(res >= k) return true;
}
return false;
}
}