思路:
给定一系列时刻表，求能满足各个时刻的最小火车数量。
打眼一看， 把此题归入到最大流，仔细一想不符合流网络的规律，换思路。
由于是一个最优化问题，自然想到动态规划和贪心。
最后确定贪心。从最早出发的火车切入，到目的地后便可以选择下一次满足的时刻表，贪心思想找最近的一个时刻表（关于贪心的证明可以参看《图论》中最大流的证明思路），反复直到找不到满足的时刻，车辆+1。之后重复该过程，一直到所有的时刻表被满足。当然，首先必须对两地的时刻表分别进行排序，复杂度O(N*N)。
思路:
给定一系列时刻表，求能满足各个时刻的最小火车数量。
打眼一看， 把此题归入到最大流，仔细一想不符合流网络的规律，换思路。
由于是一个最优化问题，自然想到动态规划和贪心。
最后确定贪心。从最早出发的火车切入，到目的地后便可以选择下一次满足的时刻表，贪心思想找最近的一个时刻表（关于贪心的证明可以参看《图论》中最大流的证明思路），反复直到找不到满足的时刻，车辆+1。之后重复该过程，一直到所有的时刻表被满足。当然，首先必须对两地的时刻表分别进行排序，复杂度O(N*N)。