- 2023 NOI省选 Day1 Day2(云斗学院版数据)
火车站(station)题解
- 2023-4-2 1:35:53 @
首先考虑有哪些站点是可达的:若站点 是可达的,则中间的每一个站点都一定是可达的(因为可以在中途切换火车轨道)。求出可达的站点区间 后,区间 中的轨道右端点和区间 中的左端点是可能的终点。
如何求出可达区间?下面以右端点 为例。在火车往右行驶时,从右端点较小的轨道切换到右端点较大的轨道更优,这启发我们按照右端点从小到大处理每个轨道,同时维护右端点 :如果 能到达这个轨道且轨道的右端点大于 ,则更新 的值。
时间复杂度 。
0 comments
No comments so far...