B4095 [CSP-X2021 山东] 口袋

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

首先，需要明确拼装目标数字

x

所需的“零件清单”。这里要注意

2

与

5

、

6

与

9

的等效性。比如目标数字是

2569

，那么我们需要统计：

2/5

类零件需要

2

个（来自

x

中的

2

和

5

），

6/9

类零件需要

2

个（来自

x

中的

6

和

9

）。其他数字则单独统计。

接着，清点口袋中的实际库存。同样需要将

2

和

5

合并统计，

6

和

9

合并统计，其余数字独立计数。

CPP

// 统计 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

次组装。

这一部分的参考代码：

CPP

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;
    }
}

B4095 [CSP-X2021 山东] 口袋

文章操作

相关推荐

评论

B4095 [CSP-X2021 山东] 口袋