走簿打穿:贪心最小成本撮合
Walking the Book: Greedy Minimum-Cost Fill
开始编码实现 solution(Q: int, offers: list[list[float]]) -> float。给定一个目标买入数量 Q(非负整数)以及一份合成订单簿 offers,每一档的形式为 [price, size](price > 0,size >= 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 可见样例;服务端提交会运行可见样例和隐藏测试。
默认展示公开样例。点击「运行样例」后会在这里显示实际输出;点击「提交评测」会进入隐藏测试。
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。