← 返回编程题库
coding-min-replenish-keep-inventory-positive中等免费版2000ms未尝试

对冲存量补货:保持非负所需的最少补货次数

Hedge-Inventory Replenishment: Minimum Top-Ups to Stay Non-Negative

开始编码

实现 solution(demand: list[int], initial: int, replenish_size: int) -> int。某做市商维护一个对冲存量账户,从 initial 单位起步,每个周期 t周期末扣减 demand[t] 单位。在任意一个周期开始之前,你可以触发任意非负次数的"补货"事件,每次补货为存量增加恰好 replenish_size 单位并计为一次。返回最少需要的补货事件总数,使得存量在每个周期末都不为负

补货发生在周期开始时,先于该期需求扣减。同一周期允许触发多次补货(且当一次补货不够覆盖单期缺口时,必须补多次)。demand 为空时返回零。某周期需求为零是允许的,不消耗任何存量。由于补货规模严格为正,问题始终可行——总能补足够多次以覆盖任意单期。

solution([3, 5, 2, 4], 4, 3) 返回 4。周期 0:存量 4 >= 3,不补货;扣减 3,存量 1。周期 1:1 < 5,缺口 4,ceil(4 / 3) = 2 次补货(累计 2),存量变为 1 + 6 = 7;扣减 5,存量 2。周期 2:2 >= 2,不补货;扣减 2,存量 0。周期 3:0 < 4,缺口 4,ceil(4 / 3) = 2 次补货(累计 4),存量变为 0 + 6 = 6;扣减 4,存量 2。共 4 次补货事件。

朴素的"每个有非零需求的周期都补一次"无视当期存量是否已经充足,是浪费;朴素的"等存量扣减完变负了再补"则违反契约——周期已经以负值收盘。预期解法是单次自左向右扫描:每周期若 inventory < demand[t] 则算缺口,按 ceil(缺口 / replenish_size) 一次性补足,再扣减需求。用闭式上取整除法(而非 while 循环),无论某周期需要多少次补货整体都保持 O(N)。

实现细节由 stubs/stub.py 提供。

实践背景

做市台的对冲存量账户在交易日内随着对外成交流而消耗,由独立的清算账户定时扫入新对冲来补货。每次扫货的批量在场所连接器里写死、每次扫货也都有运营成本——清算费、内部审批、审计入账。风险团队的提问是"按明天的预测需求路径,至少要扫多少次才能让每个周期收盘存量都不为负?"答案直接进入当日运营预算和下一交易日提交清算的预分配申请。每个交易日收盘前对下一日的预测需求路径调用一次 solution(demand, initial, replenish_size),就能给到运营一份较紧的扫货次数上界,再加一个小的安全垫即可作为正式提交。

约束条件

  • 0 <= len(demand) <= 200000;每个 demand[t] 为整数,0 <= demand[t] <= 10^12
  • 0 <= initial <= 10^12(起始存量为非负 64 位整数)
  • 1 <= replenish_size <= 10^12(每次补货事件刚好补 replenish_size 单位;严格为正)
  • 同一周期开始处可触发多次补货事件;空 demand 列表返回 0
  • 输出为非负整数,使用精确比对

样例

Case 1 · statement-example: demand [3,5,2,4] init=4 size=3 needs 4 top-ups

输入: [[3,5,2,4],4,3]

期望: 4

周期 1 缺口 4 用 ceil(4/3)=2 次补货,周期 3 缺口 4 再补 2 次,合计 4 次。

Case 2 · visible: zero demand throughout returns 0 regardless of initial

输入: [[0,0,0,0,0],0,5]

期望: 0

需求恒为零,存量从不耗尽,无需补货。

Case 3 · visible: demand[0] > initial forces top-up at period 0

输入: [[7],0,5]

期望: 2

首期需求 7 超过初始 0,缺口 7,ceil(7/5)=2 次补货。

最近提交

还没有提交记录。

编码区

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

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

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

Case 1 · statement-example: demand [3,5,2,4] init=4 size=3 needs 4 top-ups

输入: [[3,5,2,4],4,3]

期望: 4

周期 1 缺口 4 用 ceil(4/3)=2 次补货,周期 3 缺口 4 再补 2 次,合计 4 次。

Case 2 · visible: zero demand throughout returns 0 regardless of initial

输入: [[0,0,0,0,0],0,5]

期望: 0

需求恒为零,存量从不耗尽,无需补货。

Case 3 · visible: demand[0] > initial forces top-up at period 0

输入: [[7],0,5]

期望: 2

首期需求 7 超过初始 0,缺口 7,ceil(7/5)=2 次补货。