AcWing 1227. 分巧克力
原题链接
简单
作者:
长街听风
,
2021-01-24 15:02:03
,
所有人可见
,
阅读 234
java 代码
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();
int k = scanner.nextInt();
List<Segment> list = new ArrayList<>();//存储输入的所有巧克力的大小
for(int i = 0;i < n;i++ ){
list.add(new Segment(scanner.nextInt(),scanner.nextInt()));
}
int l = 1,r = 100000;//题目给出的巧克力的长宽范围,那么切分后的巧克力长宽也在该范围内
while(l < r){//结束的时候l = r,故最后输出l和输出r都是可以的
//由于是用的l = mid的模板,故这里要加1,即应向上取整,避免死循环
//(如l = 3, r = 4,则mid=3,若更新为l=mid,则区间还是3,4,无限死循环了)
int mid = l + r + 1>> 1;
if(check(list,k,mid)){//判断当切分的巧克力边长为mid时,能否切出k块出来
l = mid;//能切出k块,说明边长可以更长,故继续在[mid,r]中尝试切出更长的边长
}else{
r = mid - 1;//边长为mid时,无法切出k块,则在[l,mid-1]中找合适的边长,mid已知不行了,故是mid-1
}
}
System.out.println(l);
}
private static boolean check(List<Segment> list, int k, int mid) {
int cnt = 0;
for(Segment seg : list){
//当边长为mid时,一块大巧克力能切出的小巧克力块数为seg.length / mid * (seg.width / mid);
//注意第二个括号不能省,因为存在取整,先乘后除与先除后乘得到的结果不一样 ,如3*2/4 = 1与3*(2/4)=0不同
cnt += (seg.length / mid) * (seg.width / mid);
}
return cnt >= k;
}
}
class Segment{//代表每块巧克力的长与宽的类
public int length;
public int width;
Segment(int length,int width){
this.length = length;
this.width = width;
}
}