第八届蓝桥杯省赛 分巧克力（二分）

题目描述： 

思路：

给出N个长方形的长和宽，可以分别看长能被分成多少块，宽能被分为多少块，

也就是 (h/mid) * (w/mid),使其大于等于K

所以我们可以通过二分去找，最大的边长是多少

AC代码： 

#include<iostream>

using namespace std;

typedef long long LL;
const int N = 100010;
int n,m;
int h[N],w[N]; //巧克力长宽

bool check(int mid)
{
    LL res = 0;
    for(int i=0;i<n;i++)
    {
        //算一下巧克力长和宽分别能被切割多少块
        res += (LL)((h[i]/mid) * (w[i]/mid));
        if(res >= m) return true;
    }
    return false;
}

int main()
{
    scanf("%d%d", &n, &m);
    for(int i=0;i<n;i++) scanf("%d %d",&h[i],&w[i]);
    //巧克力的能被切割区间（边长）
    int l = 1,r = 1e5;
    //因为题目中有最大，所以用右模板
    while(l < r)
    {
        int mid = l + r + 1 >> 1;
        if(check(mid)) l = mid;
        else r = mid - 1;
    }
    printf("%d",r);
    return 0;
}