这题是上一题割绳子的二维升级版,也就是二分 + 铺瓷砖问题。 我们可以用巧克力的长和宽分别除以二分的mid值,然后相乘,这样就能切出巧克力的最大块数,而不能直接用面积去除(因为可能边角料面积会大于一整块的面积导致多计算)。
注意二分的时候mid = (l + r + 1) >> 1
,因为我们把二分的区间划分成的是[l, mid - 1]
, [mid + r]
,此时不加1会倒是二分死循环。
另外数据规模大于等于1e5
时建议使用scanf
或者快读进行读入,cin
有时候会因为读入卡常超时。
题解
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
int n, k;
pair<int, int> arr[N];
bool check(int num) {
int tot = 0;
for(int i = 0; i < n; i++) {
tot += (arr[i].first / num) * (arr[i].second / num); // 计算能切的最大块数
if(tot >= k) return true;
}
return false;
}
int main() {
cin >> n >> k;
for(int i = 0; i < n; i++) cin >> arr[i].first >> arr[i].second;
int l = 1, r = 1e5;
while(l < r) {
int mid = (l + r + 1) >> 1; // 加一防止死循环
if(check(mid)) l = mid;
else r = mid - 1;
}
cout << l << endl;
}