题目重点:同容量上限、连续液体分配,不是两桶倒水的gcd问题。
题意与假设
这道练习题保留了面经中值得训练的核心约束,并将需要澄清的条件单独列出。现场拿到变体时,先和面试官确认这些条件。
- 每桶容量上限C>0,总液体V≥0可连续分割,没有固定购买成本之外的费用。
- 字典序目标:先最少使用桶n,再让所用桶最大实际水量最小。若“最大蓄水量”指设计桶容量而非装水量,要另核合同。
解题路线
- 容量约束nC≥V,所以V>0最少n=ceil(V/C)。n固定后最大装水量≥平均V/n,均分达到下界且V/n≤C,因此最优。
- 固定第一桶装x、总x+y时,先检查0≤x≤C。剩余y最少ceil(y/C)桶,均分余桶后最高水量max(x,y/ceil(y/C))。不能为了降低最大水量多用桶,因为第一目标优先。
- Fraction保持分数精确;0体积无首桶要求时空方案。固定首桶要求即便x0也保留一个指定桶,是否算使用桶需正式确认。
手动走一遍
V10,C4:n3,每桶10/3,最大10/3;用四桶虽最大2.5更低,但桶数第一目标失败。总10,首桶x4:余6用2桶各3,最高4。x5超过C4不可行。
Python 参考实现
下面的代码按上文假设实现,适合本地运行并追加自己的测试用例。
代码区可横向滚动;使用键盘时,先聚焦代码区再按方向键查看。
from fractions import Fraction
def bucket_plan(total,capacity,first=None):
total,capacity=Fraction(total),Fraction(capacity)
if total<0 or capacity<=0:raise ValueError("nonnegative volume and positive capacity required")
def ceil_ratio(x,y):return (x/y).__ceil__()
if first is None:
if total==0:return []
count=ceil_ratio(total,capacity)
return [total/count]*count
first=Fraction(first)
if not 0<=first<=capacity or first>total:raise ValueError("invalid fixed first volume")
remaining=total-first;count=ceil_ratio(remaining,capacity)
return [first]+([remaining/count]*count if count else [])
复杂度
求数量与最高水量O(1)算术;当前代码输出n个量,时间/空间Ω(n),大n可只返回摘要。Fraction大数位成本另计。
易错点与追问
容易失分的边界
- 把均分桶数floor(V/C)会超容量。
- 液体量整数不可分时最小最大变ceil(V/n),Fraction合同不适用。
继续深挖
- 若第一桶必须x但其容量可另选,目标是否仍相同?
- 桶容量不同或部分桶有成本时为何平均分配证明失效?
