2020-2021:teams:no_morning_training:fayuanyu:cf_r639d1
差别
这里会显示出您选择的修订版和当前版本之间的差别。
| 两侧同时换到之前的修订记录 前一修订版 | |||
|
2020-2021:teams:no_morning_training:fayuanyu:cf_r639d1 [2020/05/17 17:33] 发源于 [E] |
2020-2021:teams:no_morning_training:fayuanyu:cf_r639d1 [2020/05/17 17:34] (当前版本) 发源于 [E] |
||
|---|---|---|---|
| 行 42: | 行 42: | ||
| 解：先按 ''t[i]'' 排序。由于火车不能超车，所以可以按顺序考虑火车。显然，火车 ''i'' 将路径 ''(1,s[i])'' 上所有边都置为被指向的边。这和lct是一致的。那么，对于每辆火车，执行 ''access(s[i])''， 每经过一条虚边 ''(u,v)''时， ''u'' 需要改变一次方向。 \\ | 解：先按 ''t[i]'' 排序。由于火车不能超车，所以可以按顺序考虑火车。显然，火车 ''i'' 将路径 ''(1,s[i])'' 上所有边都置为被指向的边。这和lct是一致的。那么，对于每辆火车，执行 ''access(s[i])''， 每经过一条虚边 ''(u,v)''时， ''u'' 需要改变一次方向。 \\ | ||
| 实际上，u需要在 **上次改变方向的时间** 到 **这次火车经过的时间** (''t[i]+depth[i]-1'') 这个时间区间内改变一次方向。用一个链表存每次改变方向的截至时间。 \\ | 实际上，u需要在 **上次改变方向的时间** 到 **这次火车经过的时间** (''t[i]+depth[i]-1'') 这个时间区间内改变一次方向。用一个链表存每次改变方向的截至时间。 \\ | ||
| - | 贪心，每个单位时间取所有点中下一个截止时间最近的，改变它的指向。使用堆维护，每次将一个时间弹出堆，将对应点的下个截止时间压入堆。如果堆顶已经来不及了，就输出答案。 | + | 贪心，每个单位时间取所有点中下一个截止时间最近的，改变它的指向。使用堆维护，每次将一个时间弹出堆，将对应点的下个截止时间压入堆。如果堆顶已经来不及了，就输出答案。\\ |
| + | 复杂度由lct保证，$O(n\log n)$ | ||
| =====F===== | =====F===== | ||
| 题意： | 题意： | ||
| 解： | 解： | ||
2020-2021/teams/no_morning_training/fayuanyu/cf_r639d1.1589708025.txt.gz · 最后更改: 2020/05/17 17:33 由 发源于
