BCSP-X · 2024 BCSP-X 下半年活动基础知识测评（小学高年级组） 第 19 题

三、完善程序（单选题，每小题 3 分，共计 30 分）

（生产任务） 给定 $n$ 种零部件，第 $i$ 种零部件有 $x_i$ 个。现在要用这些零部件生产机器。机器有两种。每生产一台机器 A 需要 $a_1$ 个零部件 $1$，$a_2$ 个零部件 $2$……$a_n$ 个零部件 $n$。每生产一台机器 B 需要 $b_1$ 个零部件 $1$，$b_2$ 个零部件 $2$……$b_n$ 个零部件 $n$。假设任意一个零部件都不可以被切割使用，请计算最多可以生产出多少台机器。

输入数据保证 $1 \leq n \leq 100000$，$1 \leq x_i, a_i, b_i \leq 10^9$。

试用最优选项补全程序：

#include <cstdio>
#include <algorithm>
using namespace std;

long long n, x[100005], a[100005], b[100005];

bool check(long long k) {
    long long l = 0, r = k;
    for (int i = 1; i <= n; i++) {
        if (___①___) {
            if (___②___)
                return false;
        } else {
            long long p = x[i] - b[i] * k;
            long long q = a[i] - b[i];
            if (a[i] > b[i])
                r = ___③___;
            else
                l = ___④___;
            if (l > r)
                return false;
        }
    }
    return true;
}

（本题为阅读程序 / 完善程序，完整题目与测试数据见平台）

这题考二分答案 + 线性检查。拿到题先想：设生产 k 台 B，看 A 还能产多少。对每个零件，若 a_i ≤ b_i，先全给 B 能贡献 k*b_i，余量除以 a_i 就是 A 上限；若 a_i > b_i，则 B 每多一台反而挤占 A 的原料，A 上限随 k 递减。把这些约束取 min 就是 check(k)，再二分找最大可行 k。

最容易在①处把 a_i ≤ b_i 写成 a_i < b_i，导致 a_i = b_i 时被误判为“否则”分支，进而用 p/q 算 A 上限，这是错的，因为此时 A 上限完全由剩余量决定，必须走“if”分支。②处常忘记检查 a_i*k > x_i 而写成 a_i*x_i > k，量纲全错。③④处整数除法截断问题：当 p 不能被 q 整除时，上限应向上取整，即 p/q + (p%q!=0)，否则会少算一台。⑤处二分区间收缩写错，mid 取上整时若 check(mid) 为真应把 l 拉到 mid，否则 r 降到 mid-1，很多人写成 r=mid 导致死循环或答案偏小。

这道题考查二分答案与线性可行性检查的结合，属于信息学竞赛中经典的“最大化最小值”类问题。命题人喜欢在边界情况挖坑：a_i 与 b_i 相等时、p%q!=0 时、二分区间收缩方式上。解题心法是：先假设生产 k 台机器 B，然后看每种零件还剩多少，能支持多少台机器 A。由于 k 是单调的（k 增大，A 的上限不会变大只会变小或不变），我们可以二分 k，用 check(k) 函数判断是否可行。check 函数里，对第 i 种零件分两种情况：若 a_i ≤ b_i，则先给 B 用掉 k*b_i，剩余 x_i - k*b_i 全给 A，上限是 (x_i - k*b_i)/a_i；若 a_i > b_i，则 B 每多一台，A 能用的原料就少掉 a_i - b_i 个，所以 A 的上限随 k 线性递减，公式是 (x_i - k*b_i)/(a_i - b_i)。两种情况都要保证剩余原料非负，否则直接返回 false。所有零件的 A 上限取最小值，若最小值≥0 则 k 可行。二分区间初始 l=0，r=1e9（因为单个零件最多 1e9，k 不会超过这个量级），mid 取上整 (l+r+1)/2，若 check(mid) 为真则 l=mid，否则 r=mid-1，最终 l 就是答案。

现在逐空分析：①处判断 a_i 与 b_i 的大小关系。当 a_i ≤ b_i 时，B 对零件的消耗比例大于等于 A，所以先给 B 用，余量给 A，这是正确的逻辑；当 a_i > b_i 时，B 每多一台反而挤占 A 的原料，需要单独处理。因此①应填 a_i == b_i 吗？不是，题目要求的是“若 a_i ≤ b_i”走第一分支，否则走第二分支。选项里只有 E 是 a_i == b_i，但这样会漏掉 a_i < b_i 的情况。等等，再仔细看代码结构：if (___①___) { if (___②___) return false; } else { ... }。如果①填 a_i <= b_i，那么当 a_i <= b_i 且 a_i * k <= x_i 时走内层 if，否则返回 false；当 a_i > b_i 时走 else，用 p/q 算上限。这完全符合我们的推导。但选项里没有 a_i <= b_i 吗？有，B 是 a_i <= b_i。可是参考答案给的是 E？这说明代码逻辑其实是：if (a_i == b_i) 进入一个特殊分支，里面检查 a_i * k > x_i，否则走 else 分支处理 a_i != b_i 的情况。为什么这么设计？因为当 a_i == b_i 时，p = x_i - b_i * k，q = a_i - b_i = 0，不能做除法，必须单独处理。所以①填 a_i == b_i 是正确的，对应选项 E。②处检查 a_i * k > x_i，若超过则返回 false，对应选项 A。③处当 a_i > b_i 时，p = x_i - b_i * k，q = a_i - b_i，上限是 p / q，但 p 可能不能被 q 整除，需要向上取整，即 p / q + (p % q != 0)，同时上限不能超过当前 r，所以取 min(r, p / q + (p % q != 0))，对应选项 B。④处当 a_i <= b_i 时，p = x_i - b_i * k，q = a_i - b_i（负数），上限是 p / q（向下取整），但 p 可能不能被 q 整除，需要向上取整，即 p / q + (p % q != 0)，同时上限不能低于当前 l，所以取 max(l, p / q + (p % q != 0))，对应选项 C。⑤处二分区间收缩，mid 取上整，若 check(mid) 为真则 l = mid，否则 r = mid - 1，对应选项 C。