题目描述
n块巧克力(每块高Hi宽Wi)要切出相等的k块,使每块尽可能大,(至少有k块,不能拼接)。
输出格式
输出切出的正方形巧克力最大可能的边长。
数据范围
1≤N,K≤105,
1≤Hi,Wi≤105
样例
输入样例:
2 10
6 5
5 6
输出样例:
2
C++ 代码
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=100010;
int n,k;
int h[N],w[N];
bool check(int mid){
int res=0;
for(int i=0;i<n;i++){
res+=(h[i]/mid)*(w[i]/mid);//向下取整,计算一共可分的块数是否大于K
if(res>=k)return true;
}
return false;
}
//二分
int main(){
scanf("%d%d",&n,&k);
for(int i=0;i<n;i++)scanf("%d%d",&h[i],&w[i]);
int l=1,r=1e5,mid;
while(l<r){
mid=r+l+1>>1;//因为l=mid所以是r+l+1>>1
if(check(mid))l=mid;//mid块数>=k,满足,则左边界l=mid
else r=mid-1;//否则即mid不满,则右边界r=mid-1;
}
printf("%d",l);//l或r都可
return 0;
}