B4095 [CSP-X2021 山东] 口袋

chen_zhe · 2025-03-05 11:33:52 · 题解

欢迎报名洛谷网校，期待和大家一起进步！

首先，需要明确拼装目标数字 x 所需的“零件清单”。这里要注意 2 与 5、6 与 9 的等效性。比如目标数字是 2569，那么我们需要统计：2/5 类零件需要 2 个（来自 x 中的 2 和 5），6/9 类零件需要 2 个（来自 x 中的 6 和 9 ）。其他数字则单独统计。

接着，清点口袋中的实际库存。同样需要将 2 和 5 合并统计，6 和 9 合并统计，其余数字独立计数。

// 统计 x 中的要求数量：对 2 和 5 合并计数，对 6 和 9 合并计数，其它按本身统计
int req[10] = {0};
for (int i = 0; sx[i]; i++) {
    int d = sx[i] - '0';
    if (d == 2 || d == 5) req[2]++;
    else if (d == 6 || d == 9) req[6]++;
    else req[d]++;
}

// 同样统计口袋中物品的可用数量
int avail[10] = {0};
for (int i = 0; s[i]; i++) {
    int d = s[i] - '0';
    if (d == 2 || d == 5) avail[2]++;
    else if (d == 6 || d == 9) avail[6]++;
    else avail[d]++;
}

最后，运用木桶效应原理。想象每个零件类型都是一个木桶的木板，能盛多少水取决于最短的那块。我们需要分别计算每种零件类型能支撑多少次组装（库存量 \div 需求量），最终答案就是这些计算结果中的最小值。例如，若 2/5 类能支撑 5 次，6/9 类支撑 3 次，其他零件支撑 4 次，那么最多只能完成 3 次组装。

这一部分的参考代码：

int ans = 1000000000;
if (req[2] > 0) {
    int cand = avail[2] / req[2];
    if (cand < ans)
        ans = cand;
}
if (req[6] > 0) {
    int cand = avail[6] / req[6];
    if (cand < ans)
        ans = cand;
}
// 对于其它数字：0, 1, 3, 4, 7, 8
int dgt[6] = {0, 1, 3, 4, 7, 8};
for (int i = 0; i < 6; i++) {
    int d = dgt[i];
    if (req[d] > 0) {
        int cand = avail[d] / req[d];
        if (cand < ans)
            ans = cand;
    }
}