分析
题目中$1≤H~i,W~i≤10^6$,我们可以二分枚举边长,然后算出这些巧克力可以切出的符合条件的数目,如果大于等于k,那么说明这个边长偏小了,我们就要将这个区间向右缩减,直到找到一个满足条件的最大边长。因此,我们应该使用二分模板二,即如下:
while (l < r)
{
int mid = l + r + 1 >> 1;
if (success)
{
l = mid;
}
else
{
r = mid - 1;
}
}
C++ 代码
#include <iostream>
#include <cstdio>
using namespace std;
int n, k;
int h[100005], w[100005];
bool success(int x)
{
int cnt = 0;
for (int i = 1; i <= n; i++)
{
cnt += (h[i] / x) * (w[i] / x);
}
if (cnt >= k) return true;
else return false;
}
int main()
{
scanf("%d%d", &n, &k);
for (int i = 1; i <= n; i++)
{
scanf("%d%d", &h[i], &w[i]);
}
int l = 0, r = 100005;
while (l < r)
{
int mid = l + r + 1 >> 1;
if (success(mid)) l = mid;
else r = mid - 1;
}
printf("%d\n", l);
return 0;
}
666