手机网站建设文章,互联网创业项目零成本,网站建设怎么做?,动态excel图表制作教程题目描述儿童节那天有 K 位小朋友到小明家做客。小明拿出了珍藏的巧克力招待小朋友们。小明一共有 NN 块巧克力#xff0c;其中第 i块是HiWi 的方格组成的长方形。为了公平起见#xff0c;小明需要从这 NN 块巧克力中切出 K 块巧克力分给小朋友们。切出的巧克力需要满足…题目描述儿童节那天有 K 位小朋友到小明家做客。小明拿出了珍藏的巧克力招待小朋友们。小明一共有 NN 块巧克力其中第 i块是Hi×Wi 的方格组成的长方形。为了公平起见小明需要从这 NN 块巧克力中切出 K 块巧克力分给小朋友们。切出的巧克力需要满足形状是正方形边长是整数;大小相同;例如一块 6x5 的巧克力可以切出 6 块 2x2 的巧克力或者 2 块 3x3 的巧克力。当然小朋友们都希望得到的巧克力尽可能大你能帮小明计算出最大的边长是多少么输入描述第一行包含两个整数 N,K(1≤N,K≤105)。以下 N 行每行包含两个整数 Hi,Wi (1≤Hi,Wi≤105)。输入保证每位小朋友至少能获得一块 1x1 的巧克力。输出描述输出切出的正方形巧克力最大可能的边长。输入输出样例示例输入2 10
6 5
5 6输出2运行限制最大运行时间2s最大运行内存: 256M思路二分法import java.util.Scanner;public class Main{public static void main(String[] args){Scanner sc new Scanner(System.in);int N sc.nextInt();//共有N快巧克力int K sc.nextInt();//K个小朋友\int Hi[] new int[N];int Wi[] new int[N];for(int i 0; iN ; i) {//巧克力边长Hi[i] sc.nextInt();Wi[i] sc.nextInt();}int min 1;int max 10000;int ans 0;while(minmax) {//用二分法int sum 0;int mid (max min)/2;for(int i 0;iN; i) {sum(Hi[i]/mid)*(Wi[i]/mid);}if(sumK) {max mid - 1;}else {min mid 1;ans mid;}}System.out.println(ans);}
}
