AcWing 1227. java 行行注释
原题链接
简单
作者:
季之秋
,
2021-01-16 17:22:26
,
所有人可见
,
阅读 258
取上值的二分
import java.util.*;
public class Main{
static int n,m,N=100010;
static int w[][]=new int[N][2];//最多有N个长方形
public static void main(String[] args){
Scanner sc=new Scanner(System.in);
n=sc.nextInt();
m=sc.nextInt();
for(int i=0;i<n;i++){
w[i][0]=sc.nextInt();
w[i][1]=sc.nextInt();
}
int l=0,r=100010;//长方形最长是100000,最小是0。
while(l<r){
int mid=(l+r+1)/2;//如果不加1的话 当l=r-1时,
if(check(mid)) l=mid;//l=mid =l;导致死循环
else r=mid-1;//可以画图判断取那边
}
System.out.println(r);//l和r是相等的,都可以取
}
static boolean check(int x){//判断x是不是可以分给m个小朋友
int ref=0;//x长度下可以分多少块
for(int i=0;i<n;i++){
ref+=(w[i][0]/x)*(w[i][1]/x);//宽分多少块*长可以分多少块 =长方形分多少块 。一定要加括号,面积可分但是长度不可分;
}
return ref>=m;//判断分出来的够不够小朋友每人一块
}
}