2503 分巧克力
大约 2 分钟
2503 分巧克力
【算法】 二分答案
【C++】 二分、整数除法
【难度】 普及−
一、题目简述
有 块巧克力,第 块的大小为 。需要从中切出 块大小相同的正方形巧克力(边长必须是整数),且每块正方形必须来自同一块巧克力(不能拼接)。求能切出的最大边长。
数据范围:,。
二、解题思路
1. 为什么能用二分
单调性:正方形边长 越大,能切出的块数越少。如果边长为 时能切出 ≥ 块,那么任何小于 的边长也能满足。反之,如果 不行,更大的 更不行。
判定结果单调,可以二分答案。
2. check 函数设计
check(x):对于第 块巧克力,在长 、宽 的矩形中,能切出多少个 的正方形?
- 沿长度方向能切 块
- 沿宽度方向能切 块
- 总共 块
累加所有巧克力切出的块数。注意 和 最多 ,边长最大 ,乘积用 long long 防溢出。
3. 手动模拟
2 块巧克力 和 ,需要 10 块正方形:
| 边长 | 第1块() | 第2块() | 总数 | 判定 |
|---|---|---|---|---|
| 2 | (6/2)×(5/2) = 3×2 = 6 | (5/2)×(5/2) = 2×2 = 4 | 10 | ✅ |
| 3 | (6/3)×(5/3) = 2×1 = 2 | (5/3)×(5/3) = 1×1 = 1 | 3 | ❌ |
二分过程:
- l=1, r=100000, mid=50000 → check(50000)=0 ❌
- r=49999, mid=25000 → ... ❌
- ...最终找到最大边长 = 2。
三、参考代码
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5;
int H[N], W[N];
int n, K;
bool check(int x) {
long long cnt = 0;
for (int i = 1; i <= n; i++) {
cnt += (long long)(H[i] / x) * (W[i] / x);
}
return cnt >= K;
}
int main() {
cin >> n >> K;
for (int i = 1; i <= n; i++) cin >> H[i] >> W[i];
int l = 1, r = 1e5, ans = 0;
while (l <= r) {
int mid = (l + r) / 2;
if (check(mid)) { ans = mid; l = mid + 1; }
else r = mid - 1;
}
cout << ans << endl;
return 0;
}四、复杂度分析
- 时间复杂度:,其中 是边长最大值(),。每次
check遍历 块巧克力。 - 空间复杂度:,存储每块巧克力的长宽。
