一道非常难的算法编程题：设计京沪高铁车次停站

一道非常难的算法编程题

设计京沪高铁的普通车次停站并协调本文涉及到的所有车次的运行时间。

具体要求：

1.所有车次如果出现待避只能待避标杆车或大站快车，如果该站是接轨站，可以出现跨线车待避本线车。允许出现待避停站的车。不能出现大站快车待避标杆车的情况。优先级本线标杆>跨线标杆>本线普通>跨线普通。

2.只考虑京沪高铁沿途站点的车次安排，不考虑其他区间停站。

3.京沪高铁标尺按350排图，每天6:00~24:00可以运行。每站标准停靠时间2分，待避一列车标准停靠时间7分。启停附加时间启2停3。

4.看所有车次时，尽量满足存在车次使得京沪高铁上某两个站之间都可以到达；单独看每组内的车次时，尽量每组内每个站上下行停靠数量接近。车次时间分布均匀。如果不能做到，优先级从组A依次往下排。其中北京南~济南西和南京南~上海虹桥区间内的站点无需满足此规则。

5.中途车站里，如果路过：南京南站必停，济南西站和徐州东站为节点车站，天津南站、德州东站、无锡东站、苏州北站停靠车次尽量多。

6.不考虑周末线。

7.本次安排只是部分车次，无需考虑其他车次。标杆车和大站快车停站已经给出（后续补充）。

举例：

1.组F某普通车次在徐州东站待避组A某普通车次停靠或通过。组A某普通车次在蚌埠南站待避组A某标杆车通过。组A某普通车次在南京南站待避组A某标杆车停靠。

2.组F某普通车次，只需给出在京沪高铁徐州东站~上海虹桥站之间的停站，其他区间停站无需考虑。

4.例如所有车次，德州东站往返于苏州北站各有7趟，且每1个半小时就有停靠时间相对均匀。组F内，蚌埠南站往返均停靠4趟。苏州北站和镇江南站往返车次数目以及无需考虑。

组A：纯京沪高铁本线

1.北京南~上海虹桥

标杆车10对，沿途停靠站为

车次1：南京南 1

车次2：南京南 1

车次3：南京南 1

车次4：南京南 1

车次5：南京南 1

车次6：南京南 1

车次7：天津南 南京南 2

车次8：南京南 徐州东 2

车次9：南京南 苏州北 2

车次10：无锡东 南京南 2

车次11：济南西 南京南 2

车次12：南京南 济南西 2

车次13：济南西 南京南 2

车次14：南京南 济南西 2

车次15：济南西 南京南 2

车次16：南京南 济南西 2

车次17：徐州东 南京南 2

车次18：南京南 天津南 2

车次19：南京南 无锡东 2

车次20：苏州北 南京南 2

普通车次30对，请安排

特殊备注：普通车次中，济南西站和徐州东站停靠约28对。

2.天津西~上海虹桥

普通车次3对，请安排

特殊备注：普通车次中，济南西站和徐州东站必停。

3.北京南~南京南

标杆车1对，沿途停靠站为

车次1：济南西 徐州东 2

车次2：徐州东 济南西 2

4.济南西~上海虹桥

普通车次2对，请安排

特殊备注：普通车次中徐州东站必停。

组B：北京南~杭州东/宁波

1.北京南~杭州东/杭州南

标杆车2对，沿途停靠站为

车次1：南京南 1

车次2：南京南 1

车次3：济南西 南京南 2

车次4：南京南 济南西 2

普通车次4对，请安排

特殊备注：普通车次中，济南西站和徐州东站必停。

2.北京南~宁波

标杆车1对，沿途停靠站为

车次1：济南西 徐州东 南京南 湖州 杭州东 5

车次2：杭州东 湖州 南京南 徐州东 济南西 5

普通车次4对，请安排

特殊备注：普通车次中，济南西站和徐州东站必停。

组C：北京南~杭州东（途经沪杭）

1.北京南~杭州东

大站快车2对，沿途停靠站为

车次1：天津南 济南西 曲阜东 徐州东 南京南 苏州北 上海虹桥 嘉兴南 8

车次2：嘉兴南 上海虹桥 苏州北 南京南 徐州东 曲阜东 济南西 天津南 8

车次3：天津南 济南西 曲阜东 徐州东 南京南 无锡东 上海虹桥 嘉兴南 8

车次4：嘉兴南 上海虹桥 无锡东 南京南 徐州东 曲阜东 济南西 天津南 8

组D：北京南~合肥南/合肥

1.北京南~合肥南/合肥

标杆车1对，沿途停靠站为

车次1：济南西 蚌埠南 2

车次2：蚌埠南 济南西 2

普通车次4对，请安排

特殊备注：普通车次中，济南西站和蚌埠南站必停，徐州东站停靠约3对。

组E：北京南~福州/厦门北/台湾（预留）

1.北京南~福州

普通车次3对，请安排

特殊备注：普通车次中，济南西站、徐州东站和蚌埠南站必停。

2.北京南~厦门北

标杆车1对，沿途停靠站为

车次1：济南西 徐州东 合肥南 黄山北 上饶 福州 莆田 7

车次2：莆田 福州 上饶 黄山北 合肥南 徐州东 济南西 7

普通车次2对，请安排

特殊备注：普通车次中，济南西站、徐州东站和蚌埠南站必停。

3.北京南~台北（预留车次）

标杆车1对，沿途停靠站为

车次1：天津南 济南西 徐州东 合肥南 黄山北 上饶 福州 7

车次2：莆田 福州 上饶 黄山北 合肥南 徐州东 济南西 天津南 7

组F：郑州东/西安北~上海虹桥

1.郑州东~上海虹桥

大站快车1对，沿途停靠站为

车次1：开封北 商丘 徐州东 南京南 无锡东 5

车次2：无锡东 南京南 徐州东 商丘 开封北 5

普通车次4对，请安排

特殊备注：普通车次中，徐州东站必停。

2.西安北~上海虹桥

标杆车1对，沿途停靠站为

车次1：郑州东 徐州东 南京南 3

车次2：南京南 徐州东 郑州东 3

大站快车1对，沿途停靠站为

车次1：洛阳龙门 郑州东 徐州东 南京南 苏州北 5

车次2：苏州北 南京南 徐州东 郑州东 洛阳龙门 5

普通车次4对，请安排

特殊备注：普通车次中，徐州东站必停。

组G：沈阳北/沈阳/沈阳南~上海虹桥

1.沈阳北/沈阳/沈阳南~上海虹桥

大站快车1对，沿途停靠站为

车次1：山海关 唐山 天津西 济南西 曲阜东 徐州东 南京南 苏州北 8

车次2：苏州北 南京南 徐州东 曲阜东 济南西 天津西 唐山 山海关 8

普通车次3对，请安排

特殊备注：普通车次中，济南西站、徐州东站必停。