AcWing 1227. 分巧克力 | 二分
原题链接
简单
作者:
KeChang
,
2024-02-28 20:29:04
,
所有人可见
,
阅读 17
#include <iostream>
#include <numeric>
#include <algorithm>
using namespace std;
const int N = 1e5 + 10;
int n, k, h[N], w[N];
bool check(int size) {
int cnt = 0;
for(int i = 1; i <= n; ++i) {
if(h[i] < size || w[i] < size) continue;
cnt += (h[i] / size) * (w[i] / size);
}
return cnt >= k;
}
int main () {
ios::sync_with_stdio(0);
cin.tie(0);
cin >> n >> k;
int l = 1, r = 1;
for(int i = 1; i <= n; ++i) cin >> h[i] >> w[i];
r = max(*max_element(h + 1, h + n + 1), *max_element(w + 1, w + n + 1));
while(l <= r) {
int mid = ((r - l) >> 1) + l;
if(check(mid)) l = mid + 1;
else r = mid - 1;
}
cout << r;
return 0;
}