官方题解（中文整理）

基于 Benjamin Qi 的官方题解整理。

核心思路

我们希望对每组数据做到 \(O(1)\) 求解。

先考虑不额外增加芯片时，Bessie 最多能拥有多少枚 A 型芯片。显然，最优做法一定是把当前所有能兑换的 B 型芯片都兑换掉，因此初始状态下最多能有：

\(A + \left\lfloor \frac{B}{c_B} \right\rfloor c_A\)

如果这个值已经不小于 \(f_A\)，那么答案就是 \(0\)。

把问题改写成“最大的失败情况”

如果答案不是 \(0\)，设答案为 \(x\)。令：

\(y = x - 1\)

那么 \(y\) 就表示：还存在某种额外芯片分配方式，使得 Bessie 依然无法达到目标时，额外芯片总数的最大值。

设额外拿到的 A 型芯片数为 \(n_A\)，B 型芯片数为 \(n_B\)，则失败条件为：

\(\left\lfloor \frac{B+n_B}{c_B} \right\rfloor c_A + (A+n_A) < f_A\)

我们要做的，就是在满足上式的所有非负整数对 \((n_A,n_B)\) 中，让 \(n_A+n_B\) 最大。

最优失败方案的形态

设

\(\mathrm{init} = A + \left\lfloor \frac{B}{c_B} \right\rfloor c_A\)

以及

\(n_{B,0} = c_B - 1 - (B \bmod c_B)\)

如果把 \(n_B\) 取得比这个更小，那么 \(B+n_B\) 还没有到下一个 \(c_B\) 的倍数前；如果不是这个余数，那么再把 \(n_B\) 增加 \(1\)，兑换次数仍然不变，却能让总芯片数更大，与“最大失败方案”矛盾。

因此，最优的 \(n_B\) 一定可以写成：

\(n_B = n_{B,0} + i c_B \qquad (i \ge 0)\)

当 \(n_B = n_{B,0}\) 时，失败所允许的最大 \(n_A\) 为：

\(n_{A,0} = f_A - 1 - \mathrm{init}\)

每让 \(i\) 增加 \(1\)，就相当于多凑出一组可兑换的 B 型芯片，因此 \(n_B\) 增加 \(c_B\)，而为了仍然失败，\(n_A\) 最多必须减少 \(c_A\)。于是：

\(n_A = n_{A,0} - i c_A\)

所以失败总数为：

\(n_A+n_B = (n_{A,0}+n_{B,0}) + i(c_B-c_A)\)

于是分两种情况：

• 如果 \(c_A \ge c_B\)，那么随着 \(i\) 增大，总数不会更优，取 \(i=0\) 即可。
• 如果 \(c_A < c_B\)，那么应尽量增大 \(i\)，直到 \(n_A\) 仍然非负，即： \(i = \left\lfloor \frac{n_{A,0}}{c_A} \right\rfloor\)

求出最大的失败总数 \(y\) 后，最终答案就是 \(y+1\)。

复杂度

每组测试只做常数次计算，时间复杂度 \(O(1)\)。