P4784 最大值（基础）

解题思路

第一步，读懂题目。 老师有 N 张长方形彩纸，每张长 W_i、宽 H_i，上面画满了 1 乘 1 的小网格。要把这些纸裁出 K 张大小相同的正方形，正方形边长必须是整数，问边长最大是多少。如果连 K 张都裁不出来，输出 -1。

第二步，把问题倒过来。 给定边长 x，一张 W 乘 H 的纸能裁出 (W/x) 乘 (H/x) 个边长为 x 的正方形。把所有纸的块数加起来，如果不少于 K，说明边长 x 可行。

第三步，发现单调性。 边长 x 越小，裁出的块数越多，越容易满足 K 张；边长 x 越大，块数越少。所以“边长 x 可行”是单调的，用二分答案在 1 到最长边之间找最大的可行边长。

第四步，处理裁不出来的情况。 与分巧克力不同的是，这里要求裁不出来时输出 -1。怎么判断呢？如果所有彩纸的面积加起来都小于 K，那么连 1 乘 1 的正方形都凑不出 K 张，直接输出 -1。

第五步，举一个例子。 两张纸分别是 4 乘 3 和 5 乘 4，要裁 K=6 张。边长 2 时：4/2 乘 3/2 = 2 乘 1 = 2 张，5/2 乘 4/2 = 2 乘 2 = 4 张，一共 6 张，可行；边长 3 时：1 乘 1 + 1 乘 1 = 2 张，不够。所以答案是 2。

第六步，注意边界。 题目保证 W_i 和 H_i 都大于 1 而且不相等。二分的上界可以取所有长和宽的最大值，因为边长再大就连一块正方形也裁不出来了。

第七步，注意裁剪的规则。 每张纸只能沿着网格线裁剪，所以块数要用整数除法（向下取整）计算，不能四舍五入。比如一张 5 乘 4 的纸裁边长为 2 的正方形，只能裁出 (5/2) 乘 (4/2) = 2 乘 2 = 4 张，剩下 1 厘米宽的边角料就用不上了，这 4 张才是有用的。

参考代码

// 最大值：二分答案求能裁出的最大正方形边长，如果连 1×1 的正方形都不够 K 块就输出 -1
#include <iostream>
using namespace std;

int paperW[105];
int paperH[105];

int main() {
    int n, k;
    scanf("%d%d", &n, &k);
    int maxSide = 0;
    for (int i = 0; i < n; i++) {
        scanf("%d%d", &paperW[i], &paperH[i]);
        if (paperW[i] > maxSide) maxSide = paperW[i];
        if (paperH[i] > maxSide) maxSide = paperH[i];
    }
    // 先检查每张纸面积之和，如果不够 K 块 1×1 的正方形，就输出 -1
    long long totalOne = 0;
    for (int i = 0; i < n; i++) {
        totalOne += (long long)paperW[i] * paperH[i];
    }
    if (totalOne < k) {
        printf("-1\n");
        return 0;
    }
    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++) {
            // 每张纸能裁出 (W/mid)*(H/mid) 个边长为 mid 的正方形
            total += (long long)(paperW[i] / mid) * (paperH[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 小于 100、边长小于 1000，运算量极小。空间 O(N)。