分巧克力(整数二分)
n个长方形,切割成m个边长为整数的正方形(不能拼接),求出可以切成的长方形的最大边长。
输入样例:n、m、以及n行长方形的长宽
2 10
6 5
5 6
输出样例:
2
思路:
整数二分:可能的答案为1、2、3......处于连续的区间里,且答案为满足切成m个正方形的分界点
枚举所有可能的边长,若能满足切成m个的要求,加大边长,选择某一区间继续二分
#include<iostream>
using namespace std;
typedef long long LL;
const int N = 100010;
int n, m;
int h[N], w[N];
bool check(int mid)
{
LL res = 0;
for(int i = 0; i < n; i++)
{
res += (h[i] / mid) * (w[i] / mid); //先把边的长度取整再乘
}
return res > m? true: false;
}
int main()
{
cin >> n >> m;
for(int i = 0; i < n; i++) cin >> h[i] >> w[i];
int l = 1, r = 1e5;
while(l < r)
{
int mid = l + r + 1>> 1;
if(check(mid)) l = mid;
else r = mid - 1;
}
cout << l;
}