题目重点：OA 题目给每服务初始吞吐、每单位扩容成本与总预算；本文二分可行阈值，并指出帖中给的样例答案与成本规则矛盾。
题意与假设
这道练习题保留了面经中值得训练的核心约束，并将需要澄清的条件单独列出。现场拿到变体时，先和面试官确认这些条件。
- 训练版吞吐量为非负整数，扩容一次恰增 1、成本为正整数且可重复扩容；预算非负。流水线吞吐为所有服务吞吐量的最小值。
- 若题目的答案 10 来自未写出的折扣、共享扩容或不同预算口径，需补原题核实；本文依正文明确的逐服务线性成本计算。
解题路线
- 若目标最小吞吐为 T，服务 i 至少需 max(0,T−throughput[i]) 次扩容，总成本 C(T)=Σmax(0,T−t_i)c_i。C(T) 随 T 单调不降，所以可二分最大可行 T。
- 下界取当前最小吞吐；任一当前瓶颈服务至少要花 minCost 才能每增加 1，故 minThroughput+budget/minCost+1 是排他的不可行上界。
- 可行性检查在费用超过 budget 时提前退出；每轮 O(n)，二分 O(log(budget/minCost+1)) 轮。
- 手算题目样例：T=6 费用为 (6−4)×3+(6−2)×5=26；T=7 费用为 9+25=34>32，答案应为 6。随机小规模与逐阈值穷举对照 10,000 组。
手动走一遍
[4,2,7]、[3,5,6]、预算 32：升至最小 6 花 6+20=26；升至 7 要 9+25=34，因此 6 是最大可行值。若强行升到 10，要 6×3+8×5+3×6=76。题目声称 10 与费用规则不一致，不能直接拿它当测试断言。
Python 参考实现
下面的代码按上文假设实现，适合本地运行并追加自己的测试用例。
代码区可横向滚动；使用键盘时，先聚焦代码区再按方向键查看。
"""Maximize the minimum pipeline service throughput under a scaling budget."""
def max_min_throughput(throughput: list[int], scaling_cost: list[int], budget: int) -> int:
if not throughput or len(throughput) != len(scaling_cost) or budget < 0:
raise ValueError("invalid input")
if any(value < 0 for value in throughput) or any(cost <= 0 for cost in scaling_cost):
raise ValueError("invalid throughput or cost")
def feasible(target: int) -> bool:
needed = 0
for value, cost in zip(throughput, scaling_cost):
needed += max(0, target - value) * cost
if needed > budget:
return False
return True
low = min(throughput)
high = low + budget // min(scaling_cost) + 1 # exclusive, impossible
while low + 1 < high:
middle = (low + high) // 2
if feasible(middle):
low = middle
else:
high = middle
return low
复杂度
n 个服务、预算 B、最小单位成本 cmin，时间 O(n log(1+B/cmin))，额外 O(1)；大整数费用在定宽语言可能溢出，提前超过预算即可短路。
易错点与追问
容易失分的边界
- 只扩容当前单个瓶颈服务，不重新检查其他服务也可能变成瓶颈。
- 把每服务成本只加一次，忘记 T−t_i 次扩容。
- 照抄题目样例答案 10，忽略它需要 76 的事实。
- 未验证成本正数或输入数组长度一致，二分上界失效。
- 二分更新界限不含等于预算的可行点。
继续深挖
- 若每次扩容收益和成本随次数变化，单调性是否仍在？
- 若服务间可以并行扩容但有每小时施工限制，怎样改模型？
- 若目标是最大总收益而非最小吞吐，为什么本题二分不适用？
