题目描述

利用二分 去寻找正方形最大可能的边
同时理解如何把长方形分解成若干个相同的正方形
如何把长方形分解成若干个相同的正方形
利用长宽比值求解
找出长与宽的公比,然后再分,正方形数量为“长除于公比”乘“宽除于公比”
left=1，因为最小巧克力的大小为1x1

样例

import java.util.*;
public class Main{

   /*
     如何把长方形分解成若干个相同的正方形
     利用长宽比值求解
            找出长与宽的公比,然后再分,正方形数量为“长除于公比”乘“宽除于公比”
    */
    static final int N = 1000010;
    static int n,k;
    static int[] p = new int[N];
    static int[] w = new int[N];

    static boolean check(int mid){
        int sum = 0;
        for(int i = 0;i<n;i++ ) sum += (long) ((p[i] / mid) * (w[i] / mid));
        if(sum >= k){
            return true;
        }
        return false;
    }

    public static void main(String[] args){
        Scanner scanner = new Scanner(System.in);
        n=scanner.nextInt();
        k=scanner.nextInt();

        for(int i = 0;i<n;i++){
            p[i]=scanner.nextInt();
            w[i]=scanner.nextInt();
        }

        int l = 1;
        int r = 100000;
        while(l<r){
            int mid = l + r + 1 >> 1;
            if(check(mid)) l=mid;
            else r = mid - 1;
        }

        System.out.print(r);
    }

}