合并 K 条交易所成交磁带
Merge K Sorted Trade Streams
开始编码跨场所执行的回放、TCA(交易成本分析)的统一原始磁带、夜里的合规归档——这些下游消费者拿到的是一条按全局时间升序排好的成交流,每一笔都打上来源场所标签。但上游推过来的是 K 条独立的磁带:tapes[0] 来自场所 VEN-A,tapes[1] 来自场所 VEN-B,tapes[2] 来自场所 VEN-C,等等。每条磁带各自已经按时间升序——它们就是从各场所行情链路上按序解析出来的——你的工作是把这 K 条按时间归并成一条。
朴素地 concat 所有磁带再 sort 是 O(N log N),但既慢又把“输入已分别有序”这个结构信息整个丢掉了。把两条做归并合并是 O(n + m);推广到 K 条,标准答案是最小堆:把每条磁带的“当前队首”入堆,每次弹出时间戳最小的那一条写到输出、再把对应磁带的下一条压进堆。整体 O(N log K)。这正是“K 路归并”的经典形态,也是这题被放进堆/Top-K 簇的原因。
请实现 solution(tapes: list[list], venues: list[str]) -> list。tapes 是 K 条按 timestamp 升序排好的成交磁带,每条记录形如 [timestamp, price, qty];venues 是与 tapes 一一对应的场所标签列表(venues[i] 是 tapes[i] 的场所)。返回一条合并后的列表,每个元素形如 [timestamp, price, qty, venue]——也就是在原三元组末尾追加场所字段。整体按 timestamp 升序;**当多条磁带的队首时间戳完全相同时,输出顺序按 venues 列表中较小的索引优先**(即如果 venues=["VEN-A", "VEN-B", "VEN-C"],三个磁带 t=2.0 都打印同一笔,则 VEN-A 那一条先输出,再 VEN-B,再 VEN-C);同一磁带内部并列时间戳之间的相对顺序按原磁带顺序保留。空磁带 [] 允许出现,跳过即可。
例如 solution([[[1.0, 100.5, 200], [4.0, 100.9, 80]], [[2.0, 100.6, 50], [4.0, 101.0, 60]], [[3.0, 100.7, 150], [4.0, 101.1, 40]]], ["VEN-A", "VEN-B", "VEN-C"]) 应返回 [[1.0, 100.5, 200, "VEN-A"], [2.0, 100.6, 50, "VEN-B"], [3.0, 100.7, 150, "VEN-C"], [4.0, 100.9, 80, "VEN-A"], [4.0, 101.0, 60, "VEN-B"], [4.0, 101.1, 40, "VEN-C"]]。注意 t=4.0 同时出现在三条磁带,输出按 venues 列表顺序 VEN-A → VEN-B → VEN-C——这一确定性约定让下游对"同时刻多场所成交"的回放结果是 reproducible 的。
总记录数最多 20 万、K 最多 100,O(N log K) 的最小堆归并是这里的标准答案。
约束条件
- 1 ≤ K ≤ 100;len(venues) == len(tapes) == K
- 每条 tape 长度 0 ≤ m_i ≤ 50000;所有磁带总记录数 N = Σ m_i ≤ 200000
- 每条 tape 内部已按 timestamp 升序排列;同一磁带内允许 timestamp 并列,并列时保持原磁带顺序
- tapes[i][j] 形如 [timestamp, price, qty]:timestamp 是浮点秒(可正可负,|t| ≤ 1e12),price 是正浮点数,qty 是正整数
- venues 是长度为 K 的非空字符串列表,元素允许重复(极少见,但题面不禁止)
- K 个磁带中允许出现空磁带 [],跳过即可
- 返回一个列表,元素形如 [timestamp, price, qty, venue]:整体按 timestamp 升序;timestamp 并列时按 `venues` 列表中较小的索引优先输出
样例
Case 1 · example from statement (three tapes, tie at t=4.0 broken by venues order)
输入: [[[[1,100.5,200],[4,100.9,80]],[[2,100.6,50],[4,101,60]],[[3,100.7,150],[4,101.1,40]]],["VEN-A","VEN-B","VEN-C"]]
期望: [[1,100.5,200,"VEN-A"],[2,100.6,50,"VEN-B"],[3,100.7,150,"VEN-C"],[4,100.9,80,"VEN-A"],[4,101,60,"VEN-B"],[4,101.1,40,"VEN-C"]]
t=1/2/3 各自从单独磁带按升序流出;t=4.0 三条磁带同时出现,按 venues 列表顺序 VEN-A → VEN-B → VEN-C 决胜,验证 K-路归并的稳定 tie-break。
Case 2 · two tapes interleaving with single shared timestamp
输入: [[[[1,50,100],[3,50.2,200]],[[2,50.1,150],[3,50.3,250]]],["VEN-A","VEN-B"]]
期望: [[1,50,100,"VEN-A"],[2,50.1,150,"VEN-B"],[3,50.2,200,"VEN-A"],[3,50.3,250,"VEN-B"]]
K=2 退化成两路归并;t=3.0 时 VEN-A 在 venues 中索引更小,因此 VEN-A 那一条先输出。
最近提交
还没有提交记录。
编码区
实现 solution(...)。本地运行当前支持 Python 可见样例;服务端提交会运行可见样例和隐藏测试。
默认展示公开样例。点击「运行样例」后会在这里显示实际输出;点击「提交评测」会进入隐藏测试。
Case 1 · example from statement (three tapes, tie at t=4.0 broken by venues order)
输入: [[[[1,100.5,200],[4,100.9,80]],[[2,100.6,50],[4,101,60]],[[3,100.7,150],[4,101.1,40]]],["VEN-A","VEN-B","VEN-C"]]
期望: [[1,100.5,200,"VEN-A"],[2,100.6,50,"VEN-B"],[3,100.7,150,"VEN-C"],[4,100.9,80,"VEN-A"],[4,101,60,"VEN-B"],[4,101.1,40,"VEN-C"]]
t=1/2/3 各自从单独磁带按升序流出;t=4.0 三条磁带同时出现,按 venues 列表顺序 VEN-A → VEN-B → VEN-C 决胜,验证 K-路归并的稳定 tie-break。
Case 2 · two tapes interleaving with single shared timestamp
输入: [[[[1,50,100],[3,50.2,200]],[[2,50.1,150],[3,50.3,250]]],["VEN-A","VEN-B"]]
期望: [[1,50,100,"VEN-A"],[2,50.1,150,"VEN-B"],[3,50.2,200,"VEN-A"],[3,50.3,250,"VEN-B"]]
K=2 退化成两路归并;t=3.0 时 VEN-A 在 venues 中索引更小,因此 VEN-A 那一条先输出。