AcWing 1227. 分巧克力
原题链接
简单
作者:
Jerry_8
,
2024-03-04 11:15:12
,
所有人可见
,
阅读 12
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
using namespace std;
const int N= 1e5+ 10;
typedef long long LL;
int n, k;
int h[N], w[N];
bool check(int x)
{
int res= 0;
for(int i= 1; i<= n; i++)
{
res+= (int)(h[i]/ x)* (int)(w[i]/ x);//看长和宽能切出来的个数,不可以拼凑
if(res>= k) //条件成立,分得的巧克力可以更大
return true;
}
return false;
}
int main()
{
cin>> n>> k;
for(int i= 1; i<= n; i++)
{
scanf("%d%d",&h[i],&w[i]);
}
int l= 1;
int r= 1e5+ 10;
while(l< r)//一个孩子能分到的巧克力范围大小遍历,用二分
{
int mid= l+ r+ 1>> 1;
if(check(mid)) l= mid;
else r= mid- 1;
}
printf("%d", l);
return 0;
}