AcWing 1227. 分巧克力
原题链接
简单
作者:
虚实相依
,
2024-04-12 21:10:14
,
所有人可见
,
阅读 1
# 拿捏
#include<iostream>
#include<algorithm>
using namespace std;
const int N =1e5+10;
int n,k;
int maxi=0;
struct node
{
int x;
int y;
}ch[N];
//在满足总数为k块的前提下,取mid的最大值
bool check(int mid)
{
int cnt=0;
for(int i=1;i<=n;i++)
{
cnt+=(ch[i].x/mid)*(ch[i].y/mid);
}
if(cnt>=k) return true;
return false;
}
int main()
{
cin>>n>>k; //n块取k块
int tmp=0;
for(int i=1;i<=n;i++)
{
cin>>ch[i].x>>ch[i].y;
tmp=max(ch[i].x,ch[i].y);
maxi=max(maxi,tmp);
}
int l=1,r=maxi;
while(l<r)
{
int mid=l+r+1>>1;
if(check(mid)) l=mid;
else r=mid-1;
}
cout<<r<<endl;
return 0;
}