分巧克力,要求每次都是整数,且为正方形,所以应该每一次每一块的巧克力可以分成多大的取决于最短的边长。
我的思路是在输入数据的过程中找到输入的巧克力的边长的最小值,但是只能是通过部分样例数据
这是为什么呢?
因为当巧克力的的个数很多,且部分巧克力的边长很大的时候,边长很小的巧克力的个数可以忽略,不进行切分(或者长度不够,直接舍弃)
所以只需要将L=1,R定义为题目给出的数据的最大值即可,当每次的mid不符合条件时候,会自动的放缩空间
同时做了这么多二分的题目可以发现,LR的定义就是定义成题目给定的最小最大值即可,不需要自己去定义,或者人为的减小!
package day;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class 分巧克力 {
/**
* @param args
* @throws IOException
*/
static final int N=100010;
static int n=0;
static int k=0;
static int a[]=new int [N];
static int b[]=new int [N];
static long res=0;
public static boolean check ( int mid) {
res=0;
for(int i=0;i<n;i++){
res+=a[i]/mid * (b[i]/mid);
}
if(res >=k){
return true;
}
else{
return false;
}
}
public static void main(String[] args) throws IOException {
BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
String p[]=bufferedReader.readLine().split(" ");
n=Integer.parseInt(p[0]);
k=Integer.parseInt(p[1]);
int l=1,r=100001;
for(int i=0;i<n;i++){
p=bufferedReader.readLine().split(" ");
a[i]=Integer.parseInt(p[0]);
b[i]=Integer.parseInt(p[1]);
}
while(l<r){
int mid = l+r +1 >> 1;
if(check(mid)){
l=mid;
}else{
r=mid-1;
}
}
System.out.println(l);
}
}