伟 大 的 航 线 伟大的航线 伟大的航线



<mstyle mathcolor="red"> 正 解 部 分 </mstyle> \color{red}{正解部分} 正解部分

题 意 : 题意: 题意:

N o d e r Noder Noder 在穿越河流时不能停止, 所以出发的时间点决定了 N o d e r Noder Noder 是否能够通过河流, 问能够通过河流的最长持续时间.

下面考虑一艘船对 N o d e r Noder Noder 时间区间的影响, 设船头 t 1 t_1 t1​ 到达过河线, 船尾 t 2 t_2 t2​, N o d e r Noder Noder t 3 t_3 t3​ 到达该船航道, 则从下图可以看出,

时间区间 [ t 1 − t 3 , t 2 − t 3 ] [t_1-t_3,t_2-t_3] [t1​−t3​,t2​−t3​] N o e d r Noedr Noedr 不能通过河流 .

这个结论对其他船来说也成立, 所以预处理出所有的这样区间, 使用 std::set<pair> 维护区间的 ∪ ∪ ∪, 然后再求补集区间的最长长度即可 .

<mstyle mathcolor="red"> 实 现 部 分 </mstyle> \color{red}{实现部分} 实现部分

代码待补, 咕咕咕