AcWing 1227. 分巧克力
原题链接
简单
作者:
我要出去乱说
,
2021-01-30 10:17:01
,
所有人可见
,
阅读 242
#include <iostream>
using namespace std;
typedef long long LL;
const int N = 1e5 + 10;
int n, m;
int h[N], w[N];
bool check(int mid)
{
LL res = 0;
for (int i = 0; i < n; i ++ ) //遍历每块大巧克力
{
res += (LL)h[i] / mid * (w[i] / mid); //每块大巧克力有多少边长为mid的小巧克力
if (res >= m) return true; //小巧克力数量大于小朋友数量则返回真
}
return false;
}
int main()
{
cin >> n >> m;
for (int i = 0; i < n; i ++ ) cin >> h[i] >> w[i];
int l = 1, r = 1e5; //小巧克力边长范围
while (l < r) //二分出小巧克力最大边长
{
int mid = l + r + 1 >> 1; //因为要取最大值,即右端点,所以用模板二
if (check(mid)) l = mid;
else r = mid - 1;
}
cout << r << endl; //此时l和r相等
return 0;
}