【编程题目】地铁优化

nemon · 发表于 2013-9-29 14:17:51

题目

最近几年，北京的城市轨道交通得到了长足发展。截止2013年5月，北京地铁共有17条运营线路，260多座车站，长度达到456公里，日均客运量接近1000万人次，是目前世界上规模最大、最繁忙的城市地铁系统。按照规划，北京地铁仍将进行大规模建设，预计2016年底将超过660公里，2020年达到1000公里。虽然如此，与发达国家相比，北京的地铁建设仍然有提高的余地，比如有些线路过于拥挤，市民到达目的地换乘太多。
地铁运营公司信息部负责地铁运营系统的信息化建设和日常维护工作，并为公司的运营决策提供技术支持。小D是这里的一名工作人员，毕业于某名牌大学计算机系。一大早，刚上班他就接到了一个任务：最近将要召开城市轨道扩展前期研讨会，地铁公司需要根据目前情况，提供关键运营数据和预备方案，供大会讨论。小D非常兴奋，“编程改变生活”，利用计算机技术就可以改善千万人的出行，这是他最开心不过的事情了。
小D手里有一些数据，包括地铁公司所有的线路，以及某个典型时段内的进站、出站记录。第一份是地铁线路图和所有车站编号的简单示例，可以看出有的线路是环线，有的不是；有的站点是换乘站，有的不是。

// 表示注释

// 文件样例开始
1号线          // 第一行表示地铁线路的名称“地铁1号线”，非环线：因为首站和末站不同
0 苹果园       // 第一个数字表示地铁站编号，第二个字符串表示地铁站名称
1 古城          // 非换乘站：因为该站只出现在1条线路中
12 公主坟       // 换乘站：因为该站出现在不同的线路中，如下面的2号线
22 四惠东       // 该站为末站
               // 空行表示该线路结束，下面是一个新线路的开始
2号线          // 该行表示地铁线路的名称“2号线”，环线：因为首站和末站都是西直门。
35 西直门       // 第一个数字表示地铁站编号，第二个字符串表示地铁站名称
12 公主坟       // 换乘站：因为该站出现在不同的线路中，如上面的1号线
35 西直门       // 该站为末站
// 文件样例结束

说明：
1. 详细的线路和车站信息可以参见文件subway.txt，如与实际线路不同，以附件subway.txt为准
2. 线路名称是唯一的
3. 地铁站的名称和编号也是唯一的。当且仅当地铁站的名称相同时，其地铁站编号才是相同的

第二份数据是系统生成的进站、出站记录(subway.log):

// 文件样例开始
2013-08-11 12:52:15 +0800: user entered station 0 with card number 11882582700068674 and amount 88.60
// 进站记录，时间为“2013-08-11 12:52:15 +0800”，一卡通10007510374466288从地铁1号线的0号车站“苹果园”进站，卡内余额88.60

2013-08-11 13:31:00 +0800: user left station 12 with card number 11882582700068674 and amount 86.60
// 出站记录，时间为“2013-08-11 13:31:00 +0800”，一卡通10007510374466288从地铁1号线的12号车站“公主坟”出站，卡内余额为86.60

// 文件样例结束

说明：
1. 开发环境提供一份简单的进出站日志文件sample.log，包含较少的数据量，供开发测试使用
2. 一卡通的卡号可以作为一名乘客进出站的唯一标识
3. 进出站记录是完整的，只要有进站记录就有出站记录，万一出现进出站不完整的记录，请直接忽略
4. 由于数据中只有进出站的记录，而没有换乘的记录，后面做分析时，我们假设所有乘客都采用最少时间策略坐车。根据统计，地铁列车平均每站花费的时间为2分30秒（即150秒），而乘客每换乘一次平均花费的时间为3分11秒（191秒）。为了简化计算，最少时间策略的计算方法为：任意相邻两站需要花费的时间相等，均为150秒，而每进行一次换乘需要额外花费的191秒
6. 乘客在任意两站乘车时，由于采用了最少时间策略，会有唯一的乘车路线

今天小D接到的任务包括以下几点，要求今天晚上下班之前完成：

1. 地铁1号线总共多少个换乘车站？(10分)
结果要求：写入文件output1.txt，共一行：第一行是换乘车站数目

2. 根据进出站记录和最少时间的策略，每位乘客都有唯一的乘车路线，有的不需要换乘（即换乘次数为0），有的需要换乘（比如从1号线到2号线，再到13号线，需要换乘2次）。我们想知道有多少乘客必须进行换乘才能到达目的地？(25分)
结果要求：写入文件output2.txt，共一行：第一行是必须进行换乘的乘客数量，比如“1234”

3. 如果现在可以修一条新地铁，连接任意两个车站，而且不论远近，那么连接哪两个车站，使得必须进行换乘的乘客降到最低，该值变成了多少？(35 分)
结果要求：写入文件output3.txt，共两行：第一行是两个车站的编号，中间用一个空格隔开；第二行这两个车站连起来后，还必须换乘的乘客数量

4. 上下班是坐地铁的高峰时间，平均每分钟都会有大量的人涌入地铁。如果我们以1分钟作为计量单位，那么必然有一个时间段（时长一分钟，比如08:12:41到08:13:40，精确到秒），该时间段比任何其他同长的时间段涌入的人数都要多，我们称这个时间为峰值时间，计算地铁1号线的峰值时间是多少，该段时间内涌入的人数是多少？(30分)
结果要求：写入文件output4.txt，共2行，第一行为涌入的人数，第二行是时间，格式为“开始时间(空格)结束时间”，开始时间和结束时间都只包含时分秒，不需要包含年月日，比如"08:12:41 08:13:40"

说明：

数据文件：

subway.txt

subway_20130929141555.rar (2.78 KB, 下载次数: 0)

【编程题目】地铁优化

站长推荐 /4