分巧克力问题题解 | 蓝桥杯

📖 题目描述

儿童节当天有 K 位小朋友到小明家做客。小明准备了 N 块巧克力，其中第 i 块为 Hi×Wi 的长方形。需要从这些巧克力中切出 K 块形状相同、大小一致的正方形巧克力，且边长必须为整数。小朋友们希望得到的巧克力尽可能大，求能切出的最大边长。

关键条件
1. 正方形边长为整数
2. 每块巧克力可切割多块小正方形
3. 需满足至少 K 块的总需求

🔍 解题思路

🎯 为何选择二分法？

⚙️ 算法框架

int l = 1, r = max_edge;
while (l < r) {
    int mid = (l + r + 1) >> 1;  // 向上取整避免死循环
    if (check(mid)) l = mid;     // 满足条件尝试更大的边长
    else r = mid - 1;            // 不满足则缩小右边界
}
return l;

⚔️ 算法对比

暴力枚举法

for (int side = MaxSide; side >=1; side--){ 
    // 遍历计算总块数
}

二分优化法

while (l < r) {
    mid = (l + r + 1) >> 1;
    if (check(mid)) ... 
}

🚀 核心代码实现

#include <iostream>
using namespace std;
const int N = 1e5 + 10;

int h[N], w[N];
int n, k;

bool check(int mid) 
{
    long long res = 0;  // 防止大数溢出,统计巧克力可切割成多少块
    for (int i = 0; i < n; ++i) 
    {
        res += (h[i]/mid) * (w[i]/mid);
        if (res >= k) return true;  // 提前剪枝
    }
    return false;
}

int main() 
{
    cin >> n >> k;
    for (int i = 0; i < n; ++i) 
        cin >> h[i] >> w[i];


    int l = 1, r = N;
    while (l < r) 
    {
        int mid = (l + r + 1) >> 1;  // 重要！+1避免死循环
        if (check(mid)) l = mid;
        else r = mid - 1;
    }
    cout << l << endl;
    return 0;
}

💡 关键技巧

1. 防溢出处理：累加时使用 long long 类型存储总块数
2. 提前剪枝：在 check 函数中一旦满足条件立即返回，提升效率
3. 边界处理：二分时 mid 计算方式 (l + r + 1) >> 1 确保区间正确收敛

🌟 复杂度证明

• 时间复杂度：二分次数为 O(log(max_edge)) ≈ 20次，每次遍历N块巧克力 → O(N logM)
• 空间复杂度：仅需存储巧克力尺寸 → O(N)

实测可在 100ms 内处理 1e5 量级的数据，完美通过蓝桥杯评测要求
```