P4781 分巧克力（基础）

解题思路

第一步，读懂题目。 小明有 N 块长方形巧克力，第 i 块是 H_i 乘 W_i 的方格。要把它们切成长度相同、边长是整数的正方形，分给 K 个小朋友，问正方形边长最大是多少。

第二步，把问题倒过来想。 直接问“边长最大是多少”不好算，但可以反过来问：如果给定边长 x，能不能切出至少 K 块正方形？这个问题很好回答：一块 H 乘 W 的巧克力，横着能切出 H/x 条，竖着能切出 W/x 条，所以一共能切出 (H/x) 乘 (W/x) 块。把 N 块的答案加起来，如果总数不少于 K，就说明边长 x 是可行的。

第三步，发现单调性。 边长越小，切出的块数越多，越容易满足“至少 K 块”；边长越大，块数越少，越难满足。所以“边长 x 可行”这个性质是单调的：x 小的时候可行，大到一定程度就不可行了。

第四步，用二分答案找最大的可行边长。 既然性质单调，就可以在 1 到最大边长之间二分：每次取中间值 mid，算一算能不能切够 K 块。能切够，说明答案至少是 mid，往更大的方向找；切不够，就往更小的方向找。

第五步，确定边长的范围。 答案最小是 1（题目保证每人至少能拿到一块 1 乘 1 的巧克力），最大不会超过所有巧克力长和宽的最大值 maxSide。

第六步，举一个例子。 一块 6 乘 5 的巧克力，边长 2 时能切 (6/2) 乘 (5/2) = 3 乘 2 = 6 块；边长 3 时只能切 2 乘 1 = 2 块。所以想要 6 块边长 2 的正方形，边长 3 就不行了。

参考代码

// 分巧克力：二分答案，判断边长 x 时能切出多少块正方形，找出能切出至少 K 块的最大边长
#include <iostream>
using namespace std;

int h[100005];
int w[100005];

int main() {
    int n, k;
    scanf("%d%d", &n, &k);
    int maxSide = 0;
    for (int i = 0; i < n; i++) {
        scanf("%d%d", &h[i], &w[i]);
        if (h[i] > maxSide) maxSide = h[i];
        if (w[i] > maxSide) maxSide = w[i];
    }
    // 二分答案：在 [1, maxSide] 中找最大的边长，使得能切出的块数不少于 K
    int left = 1, right = maxSide, answer = 1;
    while (left <= right) {
        int mid = (left + right) / 2;
        long long total = 0;
        for (int i = 0; i < n; i++) {
            // 每块长方形能切出 (h/mid)*(w/mid) 个边长为 mid 的正方形
            total += (long long)(h[i] / mid) * (w[i] / mid);
        }
        if (total >= k) {
            answer = mid;
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    printf("%d\n", answer);
    return 0;
}

复杂度分析

二分查找最多进行 O(log maxSide) 轮，每一轮要遍历 N 块巧克力计算总数，是 O(N)。所以总时间复杂度是 O(N log maxSide)。题目中 N 和 maxSide 都不超过 10^5，大约只需要做 10^5 乘 17 次运算，非常快。空间上需要两个数组存长和宽，是 O(N)。