大致题意:第一行输入 [车站数,乘客数],后面每一行输入 [上车时间,上车车站,下车车站]。道路为环形道路,按最短路径行驶。入车站0到车站9(共11个车站)选择0-10-9的路径。每一站路耗时5分钟,问路上最多同时有几辆车?
题意是从讨论区总结的,若有偏差请指出。
自己用python3写了一段,请各位大佬指点指点
"""第一行输入车站数N,乘客数K。后面每一行为 [上车时间,上车车站,下车车站] 环形道路,按最短路径处理,问路上最多同时有几辆车""" tmp = input().split(' ') N = int(tmp[0]) # 车站数 K = int(tmp[1]) # 乘客数 arr = [] # 记录上车时间、下车时间 for k in range(K): try: tmp = input().split(' ') start = int(tmp[0]) x = int(tmp[1]) # 上车车站 y = int(tmp[2]) # 下车车站 way1 = abs(y-x) # 第一种乘坐方法 way2 = N - way1 # 第二种乘坐方法 timecost = 5*min(way1, way2) # 选择路径短的,换算成乘车时间 arr.append( [start, start+timecost] ) # 存入时间区间 except: break # 时间区间排序 arr1 = sorted(arr) # 按上车时间排序 dic = {} # 按时间点记录车辆变化,上车+1下车-1 for i in range(len(arr1)): x = arr1[i][0] # 上车时间 y = arr1[i][1] # 下车时间 dic[x] = dic.get(x, 0) + 1 # 上车,则车数加一 dic[y] = dic.get(y, 0) - 1 # 下车,则车数减一 list = sorted(dic) # 把所有时间点排序 car = [0 for i in range(len(list))] car[0] = 1 for i in range(1, len(list)): # 遍历所有时间点,获得每个时间点车辆数量 car[i] = car[i-1] + dic[ list[i] ] print(max(car))
全部评论
(4) 回帖