三流容差同步三元组计数
Three-Stream Synchronized Triple Count Within Tolerance
开始编码三条独立的参考序列 ts_a、ts_b、ts_c 在略有漂移的采样时钟下并行采样;一份 SLO 看板要的是完全同步的下标三元组数——(i, j, k) 三个采样时间戳同时落在宽度 tolerance 的同一窗口内。请实现 solution(ts_a: list[int], ts_b: list[int], ts_c: list[int], tolerance: int) -> int,返回满足 max(ts_a[i], ts_b[j], ts_c[k]) - min(ts_a[i], ts_b[j], ts_c[k]) <= tolerance 的有序三元组 (i, j, k) 个数(其中 i ∈ 0..N-1, j ∈ 0..M-1, k ∈ 0..K-1)。
ts_a、ts_b、ts_c 都是严格升序的毫秒级整数时间戳数组。三元约束 max - min <= tolerance 等价于三对两两绝对差均 <= tolerance 同时成立——只查 |ts_a - ts_b| 与 |ts_b - ts_c| 是不够的,因为外侧对 |ts_a - ts_c| 仍可越界(例如 (0, tolerance, 2*tolerance))。
边界情形:
len(ts_a) == 0时返回 0。len(ts_b) == 0时返回 0。len(ts_c) == 0时返回 0。tolerance == 0要求ts_a[i] == ts_b[j] == ts_c[k];同一份窗口加二分代码仍然成立,因为窗口塌缩为单点。
例如:
ts_a = [3, 8, 17, 26, 41]
ts_b = [4, 9, 19, 27, 60]
ts_c = [5, 7, 18, 28, 80]
tolerance = 2solution(ts_a, ts_b, ts_c, tolerance) 返回 4。三元组 (3, 4, 5) 命中,max-min = 5-3 = 2;(8, 9, 7) 命中,max-min = 9-7 = 2;(17, 19, 18) 命中,max-min = 19-17 = 2;(26, 27, 28) 命中,max-min = 28-26 = 2。下标 i=4(ts_a=41)、j=4(ts_b=60)、k=4(ts_c=80)这三个值与其他流值都不在同一窗口内,所以这三个数没有参与任何入窗三元组。
实践背景
三流同步三元组计数把两两 lockstep 检查推广到三路冗余。一组三条独立采样轨——例如主时钟、独立部署的镜像采样器、跨链路复制通道——「三路同时入窗」的三元组数正是抓取那种「两两看着没事、第三路相对前两路已经漂掉」非对称漂移模式的 SLO 指标。从数学上,三元约束的入窗计数与两两版本不一样:(0, tol, 2*tol) 在内两对上入窗、但在三元约束下出窗,所以塌缩为「两次两两检查」会把每个漂掉的三元组都多算一次。本题用的窗口加二分写法在 O(N*M*log K) 最坏代价下精确给出入窗三元组个数。
约束条件
- 0 ≤ N、M、K ≤ 1500,其中 N = len(ts_a)、M = len(ts_b)、K = len(ts_c)。参考解为 `O(N*M*log K)`。
- 0 ≤ ts_a[i]、ts_b[j]、ts_c[k] ≤ 1e9。三条流均**严格升序**(单条流内不允许重复值)。
- 0 ≤ tolerance ≤ 1e9。同步带 `max(triple) - min(triple) <= tolerance` 两端均闭(用 `<=` 而非 `<`)。
- 计数对象是有序下标三元组 `(i, j, k)`——每个跨流组合独立计数。输出为 `[0, N*M*K]` 范围内的单一整数。
- `tolerance == 0` 退化为「三条流在下标 i, j, k 上时间戳完全相同」。
- N、M、K 任一为 0 时返回 `0`(不存在任何三元组)。三者都为 0 同样返回 `0`。
- 若任一输入未严格升序,行为未定义;调用方负责输入校验。
样例
Case 1 · statement-example: four triples with tol=2
输入: [[3,8,17,26,41],[4,9,19,27,60],[5,7,18,28,80],2]
期望: 4
题面例题:tol=2 时有 4 个三元组都落在容差内 — (3,4,5)、(8,9,7)、(17,19,18)、(26,27,28);其余组合 max - min 都超出 2。
Case 2 · typical: tol=0 requires exact triple match
输入: [[1,3,5,7,9],[2,3,6,7,10],[3,4,7,8,9],0]
期望: 2
tol=0 时三条流必须共享同一时间戳;只有 3 与 7 同时出现于三条流中,故计 2。
Case 3 · typical: tolerance loose enough to match all
输入: [[1,2,3],[4,5,6],[7,8,9],100]
期望: 27
tolerance=100 远大于全部时间戳跨度,所有 3*3*3=27 个三元组都满足。
Case 4 · typical: triple constraint stricter than pairwise
输入: [[0],[3],[6],3]
期望: 0
陷阱用例:|0-3|=3、|3-6|=3 均符合两两 <=3,但 max(0,3,6)-min=6 > 3,故三元约束下计 0。
最近提交
还没有提交记录。
编码区
实现 solution(...)。本地运行当前支持 Python 可见样例;服务端提交会运行可见样例和隐藏测试。
默认展示公开样例。点击「运行样例」后会在这里显示实际输出;点击「提交评测」会进入隐藏测试。
Case 1 · statement-example: four triples with tol=2
输入: [[3,8,17,26,41],[4,9,19,27,60],[5,7,18,28,80],2]
期望: 4
题面例题:tol=2 时有 4 个三元组都落在容差内 — (3,4,5)、(8,9,7)、(17,19,18)、(26,27,28);其余组合 max - min 都超出 2。
Case 2 · typical: tol=0 requires exact triple match
输入: [[1,3,5,7,9],[2,3,6,7,10],[3,4,7,8,9],0]
期望: 2
tol=0 时三条流必须共享同一时间戳;只有 3 与 7 同时出现于三条流中,故计 2。
Case 3 · typical: tolerance loose enough to match all
输入: [[1,2,3],[4,5,6],[7,8,9],100]
期望: 27
tolerance=100 远大于全部时间戳跨度,所有 3*3*3=27 个三元组都满足。
Case 4 · typical: triple constraint stricter than pairwise
输入: [[0],[3],[6],3]
期望: 0
陷阱用例:|0-3|=3、|3-6|=3 均符合两两 <=3,但 max(0,3,6)-min=6 > 3,故三元约束下计 0。