难易程度：简单

遇到问题：原本使用哈希表来做，tle

正确思路：使用二分法确定巧克力的长宽

关于两个二分模板的认识和本题目二分的认识及拓展：

二分的条件：

• 使用二分模板的题目需要满足的一个条件是具有二段性，对于该题目有二段性，如果小于Ans,
• k这个条件会满足但是每个小朋友分到的巧克力并不大，如果大于Ans,k这个条件不一定满足，
• 所以满足二段性，并且从l->r，Ans一定是递增的

数的范围二分模板的选取：

• 有两个模板一个是mid在Ans的左边，即我们所求的目标值是在mid的右边，联合数的范围这道
• 目，求一个数的下标范围时，首先先求这个数的开始的下标值，这时即Ans在mid的左边，所以
• 应该使用int mid=l+(r-l)/2,m=mid，接着求解一个数的最后一个下标，这时即Ans在mid的
• 右边，该使用int mid=(l+1+r)/2,l=mid，这两个模板对于求解一个数的位置是没有区别的
• 但是对于这种连续重复数字的下标范围就应该分清这两个模板的区别。

本题二分模板的选取：

• 因为该题目求解的是巧克力符合条件的最大边长，所以改变量为横轴即mid所在的轴，限制Ans
• 的取值就是k这个条件，我们要求解的Ans值一定在mid的右边，因为mid左边不符合要求巧
• 克力边长最大。
• 的这个条件，什么时候才能在mid的右边呢，这也就是f函数的作用，即巧克力块数大于小朋友
• 的个数k的时候才能返回true，否则返回false,即巧克力块边长分大了，导致巧克力不够分，所* 以边长要小一点。这么一分析十分的清晰，怎么会选错模板呢！int mid=(l+1+r)/2,l=mid

机器人跳跃问题二分模板选取：

• 本题目要求的是机器人在跳越n个碉堡的过程中能量不能为0，并且成功到达最后一个碉堡，
• 开始能量的最大值。因为题目求解的是机器人所需要的初始能量，所以能量e为轴上坐标，
• 我们想要求解的是mid左边的Ans,为什么呢，因为我们要求的不就是满足条件的能量最小值嘛
• 那么满足的条件是什么呢，就是第一句话说的题目要求，在check函数中枚举路过每个碉堡的
• 能量大小，因为e1=2*e0-h[i],并且e的取值范围在1~1e5内，并且是int类型数据，在计算
• 在下一个碉堡的能量时可能爆int,所以如果e>1e5就是符合条件的，每座碉堡的最大高度就是
• 1e5,如果路过这个碉堡的能量已经大于这个最大碉堡值，那么以后的能量都是>0的，这里
• 就是贪心了，所以在for循环里只要能量>=0就可以，为什么取到等于0呢，因为这时候如果
• 是最后一个碉堡，现在机器人的能量值为0，完全符合要求。int mid=l+(r-l)/2,m=mid

代码：

#include<cstdio>
#include<iostream>
using namespace std;
const int N=1e5+10;
int h[N];
int w[N];
int n,k;

bool f(int mid){
    int q=0;
    for(int i=0;i<n;i++){
         q+=(h[i]/mid)*(w[i]/mid);
        if(q>=k)
        return true;
    }
    return false;
}
int main(){

    cin>>n>>k;
    for(int i=0;i<n;i++){
        scanf("%d %d",&h[i],&w[i]);
    }

    //求每个小朋友至少分得一块巧克力的最大巧克力边长
    //所以采用的二分模板是大于等于k的最右边的值
    int l=1,r=1e5+10;
    //巧克力的边长一定在l~r这个区间内
    while(l<r){
        int mid=(l+r+1)/2;
        if(f(mid)){
            l=mid;
        }
        else{
            r=mid-1;
        }

    }
    cout<<l;
    return 0;
}