AcWing 1227. 分巧克力
原题链接
简单
作者:
为啥过不了啊
,
2024-03-01 19:51:42
,
所有人可见
,
阅读 15
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdio>
using namespace std;
const int N=1e5+10;
int n,k;
int a[N],b[N];
bool check(int mid)
{
int res=0;
for(int i=0;i<n;i++)
{
res+=(a[i]/mid)*(b[i]/mid);
}
if(res>=k) return true;
else return false;
}
int main()
{
cin>>n>>k;
for(int i=0;i<n;i++) cin>>a[i]>>b[i];
int l=0,r=1e5;
while(l<r)
{
int mid=(l+r+1)>>1;
if(check(mid)) l=mid;
else r=mid-1;
}
cout<<r<<endl;
return 0;
}
利用二分模版,找到的是最后一个满足条件的。
临界点:
边长:r -> 满足k个人吃
变长: r+1 -> 不满足k个人吃