AcWing 1227. 分巧克力
原题链接
简单
作者:
芩渊
,
2024-07-22 21:26:56
,
所有人可见
,
阅读 2
算法1
二分 左满足右不满足,求满足最后一个解
C++ 代码
import java.io.*;
public class Main {
static int n,k;
static int []h;
static int []w;
static boolean check(int mid){
int cnt = 0;
for(int i = 0;i<n;i++){
int numH = h[i]/mid;
int numW = w[i]/mid;
cnt+=numH * numW;
}
return cnt>=k;
}
public static void main(String[] args)throws IOException {
BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter out = new BufferedWriter(new OutputStreamWriter(System.out));
String []str = in.readLine().split(" ");
n = Integer.parseInt(str[0]);
k = Integer.parseInt(str[1]);
h = new int[n];
w = new int[n];
for(int i=0;i<n;i++){
str = in.readLine().split(" ");
h[i] = Integer.parseInt(str[0]);
w[i] = Integer.parseInt(str[1]);
}
//左满足右不满足,求满足最后一个解
int l = 0,r = 100000;
while(l<r){
int mid = l + r + 1 >>1;
if(check(mid)){
l = mid;
}
else{
r = mid-1;
}
}
out.write(l+"");
out.flush();
out.close();
in.close();
}
}