题解：P8647 [蓝桥杯 2017 省 AB] 分巧克力
题目传送门
一、题目描述
小明有N块不同尺寸的巧克力，需要切出K块相同大小的正方形巧克力分给小朋友们。要求找到能满足条件的最大的正方形边长。
二、题目分析
我们需要从N块巧克力中切出K个相同大小的正方形，且这些正方形要尽可能大。关键在于如何高效地找到满足条件的最大边长。
三、解题思路
- 二分查找：正方形的可能边长范围是1到最大巧克力的最小边长，我们可以用二分法在这个范围内查找。
- 验证函数：对于每个可能的边长，计算所有巧克力能切出多少个该尺寸的正方形，判断总数是否≥K。
四、算法讲解
使用二分查找来优化搜索过程：
- 左边界l：初始为0，表示最小可能边长
- 右边界r：初始为1e5+10，表示最大可能边长
- 中间值mid：每次取中间值验证
- 验证函数check：计算所有巧克力能切出多少个mid×mid的正方形
例如样例输入：
2 10
6 5
5 6
- 当mid=2时：第一块切出(6/2)(5/2)=6块，第二块切出(5/2)(6/2)=6块，总共12≥10，满足条件
- 当mid=3时：总共只能切出4块<10，不满足条件
五、代码实现
#include <bits/stdc++.h>
using namespace std;
// #define int long long
const int N = 1e5 + 10;
int n, k;
int h[N], w[N];
// 检查是否能切出足够数量的边长为x的正方形
bool check(int x)
{
int sum = 0;
for (int i = 1; i <= n; i ++)
{
sum += (h[i] / x) * (w[i]/ x); // 计算第i块巧克力能切出的数量
if (sum >= k) return true; // 提前终止，优化效率
}
return sum >= k;
}
void solve()
{
cin >> n >> k;
for (int i = 1; i <= n; i ++)
cin >> h[i] >> w[i];
int l = 0, r = N; // 初始化二分边界
// 二分查找最大满足条件的边长
while (l + 1 != r)
{
int mid = l + r >> 1; // 等同于(l+r)/2
if (check(mid))
l = mid; // 满足条件，尝试更大的边长
else
r = mid; // 不满足条件，尝试更小的边长
}
cout << l; // 输出最终找到的最大边长
}
signed main()
{
ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
solve();
return 0;
}
六、重点细节
- 二分边界初始化：l=0，r=N（1e5+10），确保覆盖所有可能边长
- 提前终止：在check函数中，一旦sum≥k就立即返回true，优化效率
- 整数除法：计算每块巧克力能切出的数量时使用整数除法，自动向下取整
- 二分终止条件：使用l+1!=r确保正确找到边界
七、复杂度分析
- 时间复杂度：O(N log M)，其中N是巧克力数量，M是最大可能边长（1e5）
- 二分查找需要O(log M)次迭代
- 每次check函数需要O(N)时间
- 空间复杂度：O(N)，用于存储巧克力尺寸
八、总结
本题通过二分查找将问题转化为验证性问题，显著提高了效率。关键在于：
- 确定二分查找的边界
- 设计高效的验证函数
- 处理边界条件和优化计算
这种"二分答案+验证"的思路在解决最大值最小化或最小值最大化问题时非常有效。