[ABC368E] Train Delay 讲解

zrl123456 · 2024-08-25 08:33:13 · 题解

[ABC368E] Train Delay

题目考察：图论建模，思维，双指针。
题目简述：
有 m 辆火车在 n 个城市间穿梭，对于第 i 辆火车，他会在 s_i 时刻从 a_i 城市出发，在 t_i 时刻从到达 b_i 城市。
现在第 1 辆火车推迟了 ans_1 单位时间，问在使得推迟总时间最小的情况下，怎样使原本可以换乘的火车现在还可以换乘（换乘不需要时间）。
数据范围：

• 2\le n,m\le 2\times 10^5
• \forall i\in[1,m],1\le a_i,b_i\le n,a_i\ne b_i
• \forall i\in[1,m],0\le s_i<t_i\le 10^9
• 1\le ans_1\le 10^9

  要想直接跑拓扑的话，轻轻松松就卡成 \Theta(n^2) 了，不可行。

那么我们发现瓶颈是在拓展以下式子而变慢的：

但是我们发现，ans_u+t_u 这部分都是一样的，那么我们可以将其记录在 b_u 这个点上，当拓展这个式子时从这个点上取值计算就可以了。

当然，t_u\le s_v 的才有贡献，那么我们复制一份火车时程表，一个按 s_i 排序，一个按 t_i 排序，跑一个类似于双指针的东西就可以了。

时间复杂度为 \Theta(m\log m)，瓶颈在排序。

代码