AcWing 1227. 分巧克力
原题链接
简单
作者:
我是java同学
,
2023-02-07 19:52:58
,
所有人可见
,
阅读 162
二分
- 本题直接求是非常不好求的,如果用二分相当于 给题目多了一个条件——巧克力能切的最大长度,我们可以二分出巧克力可以切到的最大长度
mid
,问题转化成:可以切出多少个边长为mid
的正方形。
- 每块巧克力都是独立的,所以每块巧克力的能切的最大长度都是不一样的。并且每块巧克力只能裁剪不能拼接。裁剪是分别看每条边长与最大边长的关系,而拼接是用总面积/最大巧克力的面积,两种情况是不一样的。
#include <iostream>
using namespace std;
const int N = 100010;
typedef long long LL;
int n, k;
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);
if (res >= k) return true;
}
return false;
}
int main()
{
scanf("%d%d", &n, &k);
for (int i = 0; i < n; i ++ ) scanf("%d%d", &h[i], &w[i]);
int l = 0, r = 100000;
while (l < r)
{
int mid = l + r + 1 >> 1;
if (check(mid)) l = mid;
else r = mid - 1;
}
cout << r << endl;
return 0;
}