算法思路

这题真是坑死了
看似简单的拓扑排序，实则内涵深意。
分析：对于每辆车而言最坏的情况下会经过一千站到达终点，因为要求满足题意的最小的车站的等级，一辆车会在某一站停下来，当且仅当该站大于等于发车的站，由于要求最小值，那么取等号就是最优的，那么在某一站不停的话就代表该站等级小于所有经过并且停下俩的车站，假设停下来的车站数目为x，没有停下来的车站数目为y的话(x + y <= 1000), 由于每条未停来来的车站要向停下来的车站连一条有向边并且边权为1，那么边的数量为x*y 最坏的情况下就是x == y == 500
x * y == 250000, 有1000l=辆车因此边的数量就达到了恐怖的2.5 * 1e8 空间都会爆掉，那么有的小伙伴会说因为点只有1000条，那么我用邻接矩阵建图不就可以了吗？即使这样复杂度也是O(n * M)
M = 2.5 * 1e5 也会超时因此必须用其他方法。
这里有个常用的建图技巧： 就是当点可以分为两部分的时候并且左边的点必须都向右边的点连一条边那么可以在建立一个虚拟节点，让左边的点向虚拟节点连一条边，用虚拟节点向右边的节点连一条边，那么建立的边就可以从原来的x*y条降到x + y条极大优化了空间和时间　最终复杂度为O(n + m) m = 1e6完全ok