AcWing 1227. 分巧克力
原题链接
简单
作者:
fair
,
2024-04-11 20:01:53
,
所有人可见
,
阅读 3
#include <bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int a[N],b[N];
int n,k,res;
bool check(int bn)
{
int q=0;
for(int i=0;i<n;i++)
{
int s=a[i]/bn,d=b[i]/bn;
q+=s*d;
}
if(q>=k)
return true;
return false;
}
int qie(int &mi)
{
int l=1,r=mi;
while(l<r)
{
int mid=l+r+1>>1;
if(check(mid)) l=mid;
else r=mid-1;
}
return l;
}
int main()
{
int mi=0;
scanf("%d%d",&n,&k);
for(int i=0;i<n;i++)
{
scanf("%d%d",&a[i],&b[i]);
mi=max(mi,min(a[i],b[i]));/*有的巧克力也可以不切
这样可以找出所有巧克力能切出的最大边来作为一个极限值*/
}
res=qie(mi);
printf("%d",res);
return 0;
}