题目链接:
小巧克力的边长一定在 \(1 \sim 10^5\) 之间。
答案为在 \(1 \sim 10^5\) 之间找一个最大的数,使得所有 \(h[i]/a * w[i]/a\) 的和 \(\geqslant k\) 即可。
#include <cstdio>
#include <algorithm>
const int N = 1e5 + 10;
int n, k, h[N], w[N];
bool check(int a) {
int ans = 0;
for (int i = 0; i < n; i++) ans += (h[i] / a) * (w[i] / a);
return ans >= k;
}
int main()
{
scanf("%d%d", &n, &k);
int m = -1e9;
for (int i = 0; i < n; i++) {
scanf("%d%d", &h[i], &w[i]);
m = std::max(m, std::max(h[i], w[i]));
}
int l = 1, r = m;//这里r直接取1e5也行
while (l < r) {
int mid = (l + r + 1) >> 1;
if (check(mid)) l = mid;//如果可以分出k块,就把小巧克力的边长扩大
else r = mid - 1;
}
printf("%d", l);
return 0;
}
标签:10,巧克力,P8647,mid,蓝桥,int,ans,2017
From: https://www.cnblogs.com/pangyou3s/p/18046209