AcWing 1227. 分巧克力
原题链接
简单
作者:
新嘎坡
,
2022-01-26 15:36:34
,
所有人可见
,
阅读 168
#include<cstdio>
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);//计算每种情况下的块数
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;//二分枚举边长
while(l<r)
{
int mid=(l+r+1)/2;
if(check(mid)) l=mid;
else r=mid-1;
}
printf("%d",l);
return 0;
}