题目描述

儿童节那天有K位小朋友到小明家做客。小明拿出了珍藏的巧克力招待小朋友们。

小明共有N块巧克力，其中第 i 块是Hi x Wi的方格组成的长方形。

为了公平起见，小明需要从这 N 块巧克力中切出 K 块巧克力分给小朋友们。切出的巧克力需要满足：

形状是正方形，边长是整数；
大小相同；

例如一块 6x5 的巧克力可以切出 6块2x2 的巧克力或者 2块3x3 的巧克力。

当然小朋友们都希望得到的巧克力尽可能大，你能帮小明计算出最大的边长是多少么？

输入描述

输出描述

输出切出的正方形巧克力最大可能的边长。

输入输出样例

输入：

2 10
6 5
5 6

输出：

最终代码

1. c/c++ 【第二种是自已常用的方法】

#include<bits/stdc++.h>
using namespace std;
int n,k;
int h[100010],w[100010];


//k是人数  d是猜的最大边长
bool check(int d)
{
    int num=0;
    
    for(int i=0;i<n;i++)
        num += (h[i]/d)*(w[i]/d);
        
    if(num>=k) return true;    //够分
    else       return false;   //不够分
}


int main()
{
    cin >>n>>k;
    for(int i=0;i<n;i++)   
        //h是高度，w是宽度
        cin>>h[i]>>w[i];

    int L=1, R=100010; //R是根据：(1< Hi, Wi < 105)
//整数二分法的L、R、mid如果处理不当，极容易死循环。
//请仔细领会下面两种写法

//  第一种写法：
    while(L<R) 
    {
        int mid=(L+R+1)>>1;   //除2，向右取整
        if(check(mid))     
            L=mid;  //新的搜索区间是右半部分，所以R不变，调整L=mid；
        else               
            R=mid-1; //新的搜索区间是左半部分，所以L不变，调整R=mid–1。
    }
    
    cout << L;

    
//  第二种写法：
/*  while(L<R) 
    {
        int mid=(L+R)>>1;  //除2，向左取整
        if(check(mid))    
            L=mid+1;//新的搜索区间是右半部分，R不变，更新L=mid+1。
        else
            R=mid;  //新的搜索区间是左半部分，L不变，更新R=mid
    }
    cout << L-1;
*/
    return 0;
}