题目描述
算法1
二分
可以分析出分得的巧克力边长具有二段性,分得的巧克力边长大于最大符合条件的边长时,分不出k个巧克力,小于等于最大符合条件的边长时,可以分出k个巧克力
计算每个巧克力可以分出多少个边长为mid的正方形巧克力
巧克力的长Hi可以分出Hi/mid列正方形巧克力,巧克力的宽Wi可以提供Wi/mid行正方形巧克力,因此可以分出Hi/mid*Wi/mid个正方形巧克力
时间复杂度
$O(nlogn)$
参考文献
Java 代码
import java.util.Scanner;
// 1:无需package
// 2: 类名必须Main, 不可修改
public class Main {
static int n;
static int k;
static int[][] length;
static long sum=0;
public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
//在此输入您的代码...
n=scan.nextInt();
k=scan.nextInt();
length=new int[n+1][2];
int max=0;
for(int i=1;i<=n;i++){
length[i][0]=scan.nextInt();
length[i][1]=scan.nextInt();
sum+=1L*length[i][0]*length[i][1];
max=Math.max(max,Math.max(length[i][0],length[i][1]));
}
int l=1,r=max;
while(l<r){
int mid=l+r+1>>1;//因为对r进行修改,r=mid-1,因此需要让mid向右偏移,否则会造成死循环
if(check(mid))l=mid;
else r=mid-1;
}
System.out.print(r);
scan.close();
}
public static boolean check(int mid){
if(1L*mid*mid>sum)return false;
int sum1=0;
for(int i=1;i<=n;i++){
sum1+=(length[i][0]/mid)*(length[i][1]/mid);
}
return sum1>=k;
}
}