AcWing 1227. 分巧克力
原题链接
简单
作者:
小半
,
2024-04-04 16:44:07
,
所有人可见
,
阅读 2
#include<iostream>
using namespace std;
int const N = 1e5+10;
int w[N],h[N];
int n,k;
bool check(int a)
{
int num = 0;//记录分成长度为 a 的巧克力数量
for (int i = 0; i < n; i++)
{
num += (w[i] / a) * (h[i] / a);//每一大块可以分成的边长为 a 的巧克力数量
if (num >= k)
return true;//大于要求数量,返回真 根据这一步来判断我们下面是选l还是r 因为是num>=k 所以如果为真的话r = mid 往更大的地方去判断
}
return false;
}
int main()
{
cin>>n>>k;
for(int i=0; i<n;i++) cin>>h[i]>>w[i];
int l=1,r=1e5;
while(l<r)
{
int mid = l + (r-l+1>>1);
if(check(mid)) l = mid;
else r= mid-1;
}
cout<<r;
}