[//]: # 整数二分

题目描述

有k个小盆友，分n块，长Hn宽Wn的巧克力，切出的巧克力需要满足：

1 形状是正方形，边长是整数.
2大小相同.
得到的巧克力尽可能大，计算出最大的边长？

样例

输入：
2 10
6 5
5 6
输出：
2

二分法

根据题意，发现直接求解较难，应把最优问题转化为判断问题。
如果想到使用二分，此题就变为一个简单整数二分。

整数二分模板如下：

bool check(int x) {   } // 检查x是否满足某种性质

// 区间[l, r]被划分成[l, mid]和[mid + 1, r]时使用：
int bsearch_1(int l, int r)
{
    while (l < r)
    {
        int mid = l + r >> 1;
        if (check(mid)) r = mid;    // check()判断mid是否满足性质
        else l = mid + 1;
    }
    return l;
}
// 区间[l, r]被划分成[l, mid - 1]和[mid, r]时使用：
int bsearch_2(int l, int r)
{
    while (l < r)
    {
        int mid = l + r + 1 >> 1;
        if (check(mid)) l = mid;
        else r = mid - 1;
    }
    return l;
}

时间复杂度

O(nlogn)

参考文献

yxc视频
分享中二分算法帖子

C++ 代码

#include<iostream>
using namespace std;
const int N=100010;
int h[N],w[N],n,k;

bool check(int mid)//判断
{
    long long  res=0;
    for(int i=0;i<n;i++)
    {
        res += (long long )h[i] / mid * (w[i] / mid);
        if (res >= k) return true;
    }
    return false;
}
int main(){
    cin>>n>>k;
    for(int i=0;i<n;i++){
        cin>>h[i]>>w[i];
    }
    int l=1;int r=1e5;

    while(l<r)
    {
        int mid=l+r+1>>1;//由mid先等于l,所以用模板二
    if(check(mid)) {
       l=mid; 
    }

    else r=mid-1;
    }
    cout<<l;

    return 0;
}

相关例题

个人认为难度由小变大
AcWing：
789.数的范围
790.数的三次方根
680.切绳子
730.机器人跳跃问题
1227.分巧克力
1236.递增三元组