Day-7 分巧克力（整数二分）

考点：整数二分

AcWing 1227

思路

这道题正常想很难找到突破口,如果我们能够利用逆向思维,把它转化为一个判定问题(类似昨天的剪绳子问题),那么就会变得容易.试想,如果把N块巧克力都切成边长为mid的正方形,可以切多少块?够不够这几个小朋友分呢?如果不够怎么办?如果,切的块数多了怎么办?

这时,我们就想到用二分的方法,逐步逼近我们要找的答案.

如果不够,说明我们每一块切的太大了,这时就要减小每块的边长,使其小于mid,即在二分区间的左边找答案.反之,则要在二分区间的右边找答案(>mid)

#include <iostream>

using namespace std;

const int N = 100010;

int n,k;
int h[N],w[N];

//判断切得的总块数是否大于人数
bool check(int mid) 
{
    int cnt = 0; //cnt用来计切得的总块数
    for(int i = 0; i < n ; i ++ )
    cnt += (h[i]/mid) * (w[i]/mid);
    //如果在h[i]边上切可以切几块?如果在w[i]边上切呢?加和就是总块数.
    return cnt >= k;
}
int main()
{
    cin >> n >> k;
    for(int i = 0; i < n; i ++ )
    cin >> h[i] >> w[i];

    int l = 0,r = 1e5;
    while(l < r)
    {
        int mid = (l + r + 1) / 2;
        if(check(mid)) l = mid; //满足上面说的判定条件
        else r = mid - 1;
    }

    cout << r;
    return 0;
}