← 返回编程题库
coding-koko-eating-bananas简单免费版2000ms未尝试

最小吃香蕉速度(在答案上二分)

Minimum Eating Speed (Binary Search on the Answer)

开始编码

Koko 有 H 小时要在守卫回来之前吃完 N 堆香蕉。每小时她选一堆吃最多 K 根;剩余不足 K 时全吃完,这一小时也就过去(不能把这一小时剩下的 '吃香蕉额度' 滚到下一小时)。她想求最小整数吃速 K,使得 H 小时内能吃完所有堆。

请实现 solution(piles: list[int], h: int) -> int。速度 K 下的总小时数为

hours(K)=i=1NpiK, \mathrm{hours}(K) = \sum_{i=1}^{N} \left\lceil \frac{p_i}{K} \right\rceil,

答案即满足 hours(K)h\mathrm{hours}(K) \le h 的最小整数 K1K \ge 1。在 K[1,max(piles)]K \in [1, \max(\text{piles})]对答案二分。关键不变量是 hours(K)\mathrm{hours}(K) 关于 K 单调非增,可行性一旦达成就对所有更大速度持续保持,答案即可行后缀的左边界。

哨兵:当 h < len(piles) 时返回 -1。任何正整数 K 下每堆都至少耗 1 小时(pi/K1\lceil p_i / K \rceil \ge 1),所以 h<Nh < N 时不存在可行 K。Spec 抛 ValueError;批量打分环境编码为哨兵 -1,由于合法 K 必 1\ge 1,故 -1 明显落在合法值域之外。

例子

solution([3, 6, 7, 11], 8) 返回 4。K=4 时 hours = 3/4+6/4+7/4+11/4=1+2+2+3=88\lceil 3/4 \rceil + \lceil 6/4 \rceil + \lceil 7/4 \rceil + \lceil 11/4 \rceil = 1 + 2 + 2 + 3 = 8 \le 8,可行;K=3 时 hours = 1+2+3+4=10>81+2+3+4 = 10 > 8,不可行。谓词在 K=4 处翻转,区间 [1, 11] 上二分约 log211=4\lceil \log_2 11 \rceil = 4 步即可命中这个左边界。

solution([30, 11, 23, 4, 20], 5) 返回 30h=N=5h=N=5,每堆只能花 1 小时,所以 Kmax(piles)=30K \ge \max(\text{piles}) = 30。这是紧约束工况h=Nh=N 时答案恒为 max(piles)\max(\text{piles})

solution([3, 6, 7, 11], 27) 返回 1hh 与香蕉总数(27)相等,最慢速度 K=1 即足够:hours = 3+6+7+11=273+6+7+11 = 27 恰好。充裕工况h=pilesh = \sum \text{piles} 时答案恒为 1。

详见 stubs/stub.py 中的函数骨架。

实践背景

这是对答案二分(也叫 'parametric search'、'对单调谓词搜索')的经典训练问题——只要可行性测试便宜、最优值无法直接寻址,这一模式就普遍适用。窍门每次都一样:把 '在 P(X) 约束下最小化 X' 改写成 '找到使 P(X) 为真的最小 X',前提是 P 单调,于是在 X 上二分。

量化系统里这一模式反复出现:满足尾 VaR 约束的最小资本准备金(P(reserve) = 模拟+检查);满足限速约束的最小节流时延(P(latency) = 包轨迹回放);让蒙特卡洛路径熬过制度震荡的最小止损缓冲(P(buffer) = 路径模拟)。约束测试(P)可以很贵——全量模拟、全量回测——但只跑 O(logM)O(\log M) 次,MM 是参数范围,对比线性扫描的 O(M)O(M)。当 M=109M = 10^9 时,这是 30 次求值与 10 亿次的差别;算法本身让端到端跑约束测试变得可负担。Koko 只是个玩具壳:限速消耗对硬截止时间。真正的实例是做市台的 order router 在问 '我以多低的速率把母单切片撒出去能在收盘前清完盘口'——同一个谓词、同一个单调结构、同一次二分。整数 K 这个细节在生产环境里同样关键:很多真实节流是量化的(每秒订单数、每秒包数),把连续最优值向上取整到下一个整数可能改变答案(因为 pi/K\lceil p_i / K \rceil对每堆取上整、而非对总和取上整),所以整数二分不只是浮点问题的离散化——它就是工程师真正要发的版本。

约束条件

  • 1 <= len(piles) <= 10^4
  • 1 <= piles[i] <= 10^9
  • len(piles) <= h <= 10^9
  • 比较器:整数精确相等
  • h < len(piles) 不可行(任何正整数 K 下每堆至少耗 1 小时)。Spec 抛 ValueError;批量打分环境编码为哨兵返回值 -1(合法 K 必 >= 1,故 -1 落在合法值域之外)
  • 参考解搜索区间为 [1, max(piles)],标准左边界二分不变量:hours(hi) <= h 始终成立、hours(lo) > h 或 lo == 1

样例

Case 1 · LC875 canonical: piles=[3,6,7,11] h=8 -> K=4

输入: [[3,6,7,11],8]

期望: 4

LeetCode 875 经典样例。K=4 时 hours = ceil(3/4)+ceil(6/4)+ceil(7/4)+ceil(11/4) = 1+2+2+3 = 8 <= 8 可行;K=3 时 hours = 1+2+3+4 = 10 > 8 不可行。可行性谓词在 K=4 处发生翻转,二分定位到这个左边界。

Case 2 · LC875: piles=[30,11,23,4,20] h=5 -> K=30 (h=N tight)

输入: [[30,11,23,4,20],5]

期望: 30

h=N=5 紧约束。每堆只能花 1 小时,因此 K 至少要 >= max(piles)=30,恰好等于最大堆。这检验上界 K=max(piles) 总是可行。

Case 3 · LC875: piles=[30,11,23,4,20] h=6 -> K=23

输入: [[30,11,23,4,20],6]

期望: 23

再给一小时缓冲,最大堆 30 可以拆成两小时,K 降到 23。验证非紧约束工况下二分能跨过若干候选 K 值。

Case 4 · h = sum(piles): K=1 (slowest feasible)

输入: [[3,6,7,11],27]

期望: 1

h 等于香蕉总数 27,K=1 时 hours = 3+6+7+11 = 27 恰好满足。K=1 是定义域下界且此时可行,验证下界总在可行集中的边角工况。

Case 5 · single pile N=1: ceil(p/K) <= h

输入: [[1000000000],2]

期望: 500000000

单堆 10^9,h=2,需 ceil(10^9/K) <= 2,最小 K = 5*10^8。验证 N=1 退化为单变量 ceil 不等式,且二分上界 max(piles)=10^9 处 hours=1,下界 K=1 处 hours=10^9,需要二分压到中间。

Case 6 · single pile h huge -> K=1

输入: [[1000000000],1000000000]

期望: 1

h=10^9 与堆大小相等,K=1 即可在 10^9 小时内吃完。验证 h 充裕时下界 K=1 直接是答案。

最近提交

还没有提交记录。

编码区

实现 solution(...)。本地运行当前支持 Python 可见样例;服务端提交会运行可见样例和隐藏测试。

加载编辑器...
计时0:00

默认展示公开样例。点击「运行样例」后会在这里显示实际输出;点击「提交评测」会进入隐藏测试。

Case 1 · LC875 canonical: piles=[3,6,7,11] h=8 -> K=4

输入: [[3,6,7,11],8]

期望: 4

LeetCode 875 经典样例。K=4 时 hours = ceil(3/4)+ceil(6/4)+ceil(7/4)+ceil(11/4) = 1+2+2+3 = 8 <= 8 可行;K=3 时 hours = 1+2+3+4 = 10 > 8 不可行。可行性谓词在 K=4 处发生翻转,二分定位到这个左边界。

Case 2 · LC875: piles=[30,11,23,4,20] h=5 -> K=30 (h=N tight)

输入: [[30,11,23,4,20],5]

期望: 30

h=N=5 紧约束。每堆只能花 1 小时,因此 K 至少要 >= max(piles)=30,恰好等于最大堆。这检验上界 K=max(piles) 总是可行。

Case 3 · LC875: piles=[30,11,23,4,20] h=6 -> K=23

输入: [[30,11,23,4,20],6]

期望: 23

再给一小时缓冲,最大堆 30 可以拆成两小时,K 降到 23。验证非紧约束工况下二分能跨过若干候选 K 值。

Case 4 · h = sum(piles): K=1 (slowest feasible)

输入: [[3,6,7,11],27]

期望: 1

h 等于香蕉总数 27,K=1 时 hours = 3+6+7+11 = 27 恰好满足。K=1 是定义域下界且此时可行,验证下界总在可行集中的边角工况。

Case 5 · single pile N=1: ceil(p/K) <= h

输入: [[1000000000],2]

期望: 500000000

单堆 10^9,h=2,需 ceil(10^9/K) <= 2,最小 K = 5*10^8。验证 N=1 退化为单变量 ceil 不等式,且二分上界 max(piles)=10^9 处 hours=1,下界 K=1 处 hours=10^9,需要二分压到中间。

Case 6 · single pile h huge -> K=1

输入: [[1000000000],1000000000]

期望: 1

h=10^9 与堆大小相等,K=1 即可在 10^9 小时内吃完。验证 h 充裕时下界 K=1 直接是答案。