← 返回编程题库
coding-greedy-min-cost-fill中等免费版2000ms未尝试

走簿打穿:贪心最小成本撮合

Walking the Book: Greedy Minimum-Cost Fill

开始编码

实现 solution(Q: int, offers: list[list[float]]) -> float。给定一个目标买入数量 Q(非负整数)以及一份合成订单簿 offers,每一档的形式为 [price, size]price > 0size >= 1)。返回严格按从低价到高价吃簿所能得到的最小总成本——同价档之间任意排列都得到同样的总成本,而最后一档可能被部分消耗:只买入还需要的那部分股数,不必把整档吃完。

Q == 0,返回 0.0;若 sum(size for price, size in offers) < Q(即全部档位加起来都凑不齐 Q 股),返回 -1.0,表示这一目标在当前簿上不可成交。

solution(6, [[10.5, 3], [9.0, 4], [11.0, 5]]) 返回 57.0。按价格升序重排后是 [[9.0, 4], [10.5, 3], [11.0, 5]]:先把 [9.0, 4] 整档吃完(4 * 9.0 = 36.0),剩余 2 股从 [10.5, 3]部分消耗(2 * 10.5 = 21.0),合计 36.0 + 21.0 = 57.0,第三档 [11.0, 5] 完全未被触碰。

朴素的"每股扫描一遍 offers 找最便宜档"是 O(Q*N),在 Q 接近 1e12 的隐藏用例上无法在 2 秒内跑完。期望解法:先按价格升序排序,再从前往后累加 size * price,途中维护剩余需买量;当某档 size > remaining 时只买 remaining * price 并立即返回。同时完整算出 sum(size)Q 比较——只在确认可行后才进入累加路径。

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

实践背景

在执行端,"如果我现在按某 VWAP 切片把这一笔单挂出去吃簿,最便宜需要花多少?"是定盘价基准(cost-basis benchmark)的标准计算;它给出的是路由器在没有任何对手抢跑、没有价格滑落的"理想极限",自然也成了实盘真实成本回归到该基准的差额——也就是滑点 (slippage) 的定义。solution(Q, offers) 把"贪心吃簿"这一原语单独拎出来:在策略实测里,它每个 tick 都会被调用以更新策略 PnL 的"盈亏归因到簿"分项;在合规端,它也用于"如果一定要立即清掉这部分库存,最优情形下要付多少?"的强平估算。算法本身只是"排序加累加"的简单贪心,但在执行台账上它是可被反复引用的基础积木。

约束条件

  • 0 <= Q <= 10^12(target 数量为非负 64 位整数)
  • 0 <= len(offers) <= 200000;每个 offers[i] = [price, size],其中 price 为正浮点数(price > 0),size 为正整数(size >= 1)
  • 供给侧不保证按价格排序;同价位允许多笔 offer,且其相对顺序不影响最终成本
  • 若 Q == 0,返回 0.0;若 sum(size) < Q(总供给不足),返回 -1.0
  • 输出为浮点总成本,使用浮点比较,rel_tol = 1e-9,abs_tol = 1e-12

样例

Case 1 · statement-example: walk-the-book partial last fill

输入: [6,[[10.5,3],[9,4],[11,5]]]

期望: 57

按升序排序后吃满 [9.0,4] 得 36.0,再从 [10.5,3] 部分吃 2 股得 21.0,合计 57.0;[11.0,5] 不被触碰。

Case 2 · visible: infeasible total supply < Q returns -1.0

输入: [10,[[1,4],[2,5]]]

期望: -1

总供给 4+5=9 严格小于 Q=10,直接返回 -1.0,不进入累加。

Case 3 · visible: Q == 0 returns 0.0 regardless of offers

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

期望: 0

目标数量为 0,直接返回 0.0,不查 offers。

最近提交

还没有提交记录。

编码区

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

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

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

Case 1 · statement-example: walk-the-book partial last fill

输入: [6,[[10.5,3],[9,4],[11,5]]]

期望: 57

按升序排序后吃满 [9.0,4] 得 36.0,再从 [10.5,3] 部分吃 2 股得 21.0,合计 57.0;[11.0,5] 不被触碰。

Case 2 · visible: infeasible total supply < Q returns -1.0

输入: [10,[[1,4],[2,5]]]

期望: -1

总供给 4+5=9 严格小于 Q=10,直接返回 -1.0,不进入累加。

Case 3 · visible: Q == 0 returns 0.0 regardless of offers

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

期望: 0

目标数量为 0,直接返回 0.0,不查 offers。