分巧克力（二分法）

题目地址：https://www.dotcpp.com/oj/problem1885.html

 

分析：

我们知道，在1~100000之间的任何一个数x，将各个“大块的巧克力”按照边长为x的正方形进行切割，如果切割的块数大于等于K，就能够实现每个小朋友都有一份的目标。我们要找的是最大的那个x，

不妨记为maxX（如果最大值为maxX，那么1到maxX之间的任何数x都可以作为正方形巧克力的边长）。该题乍一看似乎与查找没关系，但是仔细分析，可以将原问题理解为：在1~100000之间寻找一个maxX，

使得将巧克力按照边长maxX进行切分，切分成的份数要大于等于K，而如果按照maxX+1进行切割，将不再能够切出K块。如果从1-100000逐个查找，那么肯定超时，所以采用二分查找。

那如何判断能否以mid为边长分割出大于等于K块正方形巧克力呢？假设n块巧克力的长和宽分别保存在两个一维数组H[100000]和W[100000]的n个元素里。

由于一块大小为H*W（长为H，宽为W）的巧克力，可以切割成的边长为mid的正方形巧克力的块数为：(H/mid)*(W/mid)，所以n块巧克力所切割成的总块数count可以按照下面的方式计算出来：

int cnt = 0;

for(int i = 1; i<= n; i++)

{

    cnt+= (H[i]/x)*(W[i]/x);

 }

显然当cnt大于等于K时，就可以切割出能够分给小朋友的巧克力，否则就切割不出。

 

#include <iostream>
#include <cstring>

using namespace std;

int n, k, a[110000], b[110000];

bool ok(int x)
{
    int cnt = 0;
    for (int i = 1; i <= n; i++)
    {
        cnt += (a[i] / x)*(b[i] / x);
        if (cnt >= k)
            return true;
    }

    return false;
}

int main()
{

    cin >> n >> k;
    for (int i = 1; i <= n; i++)
        cin >> a[i] >> b[i];
        
    int l = 0;
    int r = 100004;

    while (r - l > 1) 
    {
        int m = (l + r) / 2;
        if (ok(m))
            l = m;
        else 
            r = m;
    }
    cout << l << endl;

    return 0;
}