AcWing 1227. 分巧克力——二分第二种
原题链接
简单
作者:
luckdog
,
2024-02-28 20:33:53
,
所有人可见
,
阅读 15
#include<iostream>
using namespace std;
typedef long long LL;
const int N=100010;
int n,k;
int h[N],w[N]; //h*w会爆int
bool check(int mid) //二分
{
LL res=0; //表示可以切出来的个数要>=k
for(int i=1;i<=n;i++) //枚举所有长方形
{
res+=(LL)h[i]/mid*(w[i]/mid);
if(res>=k) return true;
}
return false;
}
int main() //只能切,不能拼,每个长方形最大能切多少,且切的每个正方形一样
{
cin>>n>>k;
for(int i=1;i<=n;i++) cin>>h[i]>>w[i];
int l=1,r=1e5;
while(l<r)
{
int mid=(l+r+1)/2; //mid在右区间,要向上取整
if(check(mid)) l=mid; //当取mid成立时,答案在右区间,因为要求一个最大值
else r=mid-1; //当取mid不成立时,答案在左区间
}
cout<<l<<endl;
return 0;
}