AcWing 1227. 分巧克力
原题链接
简单
作者:
Cathyqiii
,
2024-03-04 20:46:20
,
所有人可见
,
阅读 46
思路:二分查找,将边长保存在数组中,用check函数找出最大的k值。
C++ 代码
#include<bits/stdc++.h>
using namespace std;
const int N = 1e5+5;
int H[N], W[N];
int n, k;
bool check(int x) {
int sum = 0;
for (int i = 0; i < n; i++) {
sum += (H[i] / x) * (W[i] / x);
}
return sum >= k;
}
int main() {
cin >> n >> k;
for (int i = 0; i < n; i++) {
cin >> H[i] >> W[i];
}
int l = 1, r = 1e5 + 1, maxSize = 0;
while (l <= r) {
int mid = (l + r) / 2;
if (check(mid)) {
maxSize = mid;
l = mid + 1;
} else {
r = mid - 1;
}
}
cout << maxSize;
return 0;
}