思路:

给定一系列时刻表,求能满足各个时刻的最小火车数量。

打眼一看, 把此题归入到最大流,仔细一想不符合流网络的规律,换思路。

由于是一个最优化问题,自然想到动态规划和贪心。

最后确定贪心。从最早出发的火车切入,到目的地后便可以选择下一次满足的时刻表,贪心思想找最近的一个时刻表(关于贪心的证明可以参看《图论》中最大流的证明思路),反复直到找不到满足的时刻,车辆+1。之后重复该过程,一直到所有的时刻表被满足。当然,首先必须对两地的时刻表分别进行排序,复杂度O(N*N)。

05-11 02:49