问题描述

　　儿童节那天有K位小朋友到小明家做客。小明拿出了珍藏的巧克力招待小朋友们。
　　小明一共有N块巧克力，其中第i块是Hi x Wi的方格组成的长方形。
　　为了公平起见，小明需要从这 N 块巧克力中切出K块巧克力分给小朋友们。切出的巧克力需要满足：
　　1. 形状是正方形，边长是整数
　　2. 大小相同
　　例如一块6x5的巧克力可以切出6块2x2的巧克力或者2块3x3的巧克力。
　　当然小朋友们都希望得到的巧克力尽可能大，你能帮小Hi计算出最大的边长是多少么？

输入格式

　　第一行包含两个整数N和K。(1 <= N, K <= 100000)
　　以下N行每行包含两个整数Hi和Wi。(1 <= Hi, Wi <= 100000)
　　输入保证每位小朋友至少能获得一块1x1的巧克力。

输出格式

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

样例输入

2 10
6 5
5 6

样例输出

2

思路

　　看到题目第一眼，暴力，你问我超时怎么办？二分暴力了解一下。解释一下这里的二分查找为什么不能+1，普通的二分查找要+1是因为已经确定了mid不是他需要查找的值，而我们这里的二分，judge函数返回1的意思是指mid满足题意，然后我们假设mid+1就不满足题意，如果我们head=mid+1，正确答案就被删掉了。
　　关于最后多加了一步，上面我们说到了head=mid，不能加一，对应的，这里回出现死循环，所以把循环条件缩小一下，再加一步判断就AC了。

AC代码

#include<iostream>
using namespace std;
int n,m,a[100005][2];
int judge(int len)
{
    int sum=0;
    for (int i=0;i<n;i++)
    sum+=(a[i][0]/len)*(a[i][1]/len);
    if (sum>=m)
    return 1;
    else 
    return 0;
}
int main()
{
    cin>>n>>m;
    int head,mid,next;
    int i,j;
    for (i=0;i<n;i++)
    cin>>a[i][0]>>a[i][1];
    head=0,next=100000;
    while (head<next-1)
    {
        mid=head+(next-head)/2;
        if (judge(mid))    //判断当蛋糕长度为mid时，能否切出满足题意的蛋糕
        head=mid;          
        else
        next=mid-1;
    }
    if (judge(next))
    cout<<next;
    else
    cout<<head;
}