← 返回编程题库
coding-three-stream-synchronized-triple-count中等免费版2000ms未尝试

三流容差同步三元组计数

Three-Stream Synchronized Triple Count Within Tolerance

开始编码

三条独立的参考序列 ts_ats_bts_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_ats_bts_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 = 2

solution(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 可见样例;服务端提交会运行可见样例和隐藏测试。

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

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

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。