思路 （二分）

题意；就是让我们在1~100000中找到一个最大的ans,让其满足，我们能在大巧克力中划分出的小巧克力块数 >=m ;
思路；
假设n块巧克力的长和宽分别保存在两个一维数组a[100000]和b[100000]的n个元素里。
由于一块大小为 xy（长为x，宽为y）的巧克力，可以切割成的边长为mid的正方形巧克力的块数为：(x/mid)(y/mid)， 所以n块巧克力所切割成的总块数idxt可以按照下面的方式计算出来：

bool f(int x){
    int idx=0;
    for(int i=1;i<=n;i++){
        idx+=int(a[i]/x)*int(b[i]/x);
        if(idx>=m)return true;
    }
    return false;
}

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

算法1

(二分) $O(nlogn)$

C++ 代码

#include<bits/stdc++.h>
using namespace std;
const int N=100010;
int n,m;
int a[N],b[N];//存储长和宽
bool f(int x){
    int idx=0;
    for(int i=1;i<=n;i++){
        idx+=int(a[i]/x)*int(b[i]/x);//选择idx
        if(idx>=m)return true;
    }
    return false;
}
int main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++)cin>>a[i]>>b[i];//分别读入长和宽
    int l=0,r=100010;//先初始化端点的值
    //开始二分搜索
    while(r-l>1){
        int mid=(l+r)>>1;
        if(f(mid))l=mid;
        else r=mid;
    }
    cout<<l<<endl;
    return 0;
}