P4785 实验室的金属块（基础）

解题思路

第一步，读懂题目。 实验室有 n 根金属，每根长 a、宽 b、高 c，体积是 a 乘 b 乘 c。要把金属切成体积相同的小块，装进 k 个罐子里，每根金属最多装进 z 个罐子，金属可以有剩余。问小块的最大体积是多少。

第二步，把问题倒过来。 给定小块体积 x，第 i 根金属能切的块数就是它的体积除以 x（向下取整）。但注意：题目说每根金属最多装 z 个罐子，所以即使它能切更多块，块数也不能超过 z。要取 min(体积/x, z)。

第三步，判断可行性。 把所有金属的块数加起来，如果不少于 k，说明体积 x 可行；否则不可行。体积 x 越大，切出的块数越少，所以“体积 x 可行”是单调的，用二分答案找最大的可行体积。

第四步，为什么每根要限制 z？ 因为题目明确规定“每种金属不能超过 z 个罐子”，意思是同一种金属即使体积很大、能切成很多块，也不能放进超过 z 个罐子里。所以判断可行性时一定要对每根金属取 min，否则会算出偏多的块数，得到错误答案。

第五步，注意数据类型。 a、b、c 都是正整数，乘积可能达到几十万甚至更大，要用 long long 保存体积和总数，避免 int 溢出。

第六步，举一个例子。 一根 27 乘 95 乘 42 的金属，体积是 107730，z=25。如果小块体积 x 等于 107730，它能切 1 块；如果 x 比它大，它一块也切不出。

第七步，理解 z 限制如何起作用。 举个例子：如果一根金属的体积是 100000，而 z 只有 2，那么即使体积 x 很小、理论上能切出很多块，也只能算 2 块，多出来的块数要舍弃。加上这个限制后，如果所有金属加起来的块数还是不够 k，就说明体积 x 太大了，要往小的方向继续找。

参考代码

// 实验室的金属块：二分答案求最大体积，每根金属切成体积为 x 的块数 = 体积/x，且每种金属最多 z 块
#include <iostream>
using namespace std;

long long metalVolume[100005];
int z[100005];

int main() {
    int n, k;
    scanf("%d%d", &n, &k);
    long long maxVolume = 0;
    for (int i = 0; i < n; i++) {
        long long a, b, c;
        scanf("%lld%lld%lld%d", &a, &b, &c, &z[i]);
        metalVolume[i] = a * b * c;
        if (metalVolume[i] > maxVolume) maxVolume = metalVolume[i];
    }
    long long left = 1, right = maxVolume, answer = 0;
    while (left <= right) {
        long long mid = (left + right) / 2;
        long long total = 0;
        for (int i = 0; i < n; i++) {
            // 第 i 根金属能切出的块数，不能超过 z[i]
            long long count = metalVolume[i] / mid;
            if (count > z[i]) count = z[i];
            total += count;
        }
        if (total >= k) {
            answer = mid;
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    printf("%lld\n", answer);
    return 0;
}

复杂度分析

二分答案做 O(log maxVolume) 轮，每轮遍历 n 根金属计算块数，是 O(n)。总时间复杂度 O(n log maxVolume)。空间 O(n)，存每根金属的体积和上限 z。