赞
踩
代码注释非常详细
张三购买了一辆续航里程数达到1000公里的自动驾驶车。
一天车电充满后,从甲城出发,前往距离d km的乙城。全程走高速。
沿途有n个休息站,可提供充电服,充电站提供了当前充电的排队时间。
高速上的行程速度固定为100公里每小时, 汽车可以将电全部用光。1000公里续航的汽车,如果按100公里每小时奔跑,可以跑十个小时
每次充电时间固定为一个小时【不考虑之前的剩余电量】,每次充电后电池充满,排队过程不耗电
输入格式
第一行是甲乙两地的距离d【0<=d<=1000000】, 单位km 【d是100的倍数】
第二行的充电站的个数n 【0<=n<=10000】
第3行开始,每行2个数据,分别是充电站离甲城的距离和等待的时间(单位小时)
输出
能到达终点输出最短的时间(小时),否则输出-1
import sys # d公里数,是100的倍数 n休息站的数量 d = int(input()) n = int(input()) # lst存储充电站的坐标和等待时间,这里巧妙的将甲地也当作一个充电站,甲地坐标为0 lst = [[0, 0]] # 输入n个充电站数据 for i in range(1, n + 1): lst.append(list(map(int, input().split()))) # 巧妙的将乙地也当作一个充电站 lst.append([d, 0]) # dp数组 dp[i]表示到达第i号充电站并在第i个充电站充电后花费的最短充电时间 # 【没有计算沿途驾驶时间,因为在路上开车的时间是固定的,为d/100】 # 我们把甲第当作一个序号0【第0个】的充电站 dp = [0] #遍历第1~n+1号充电站,我们把乙地当作n+1号充电站 for i in range(1, n + 2): site = lst[i][0] time = lst[i][1] # 一开始设置一个大点的数 dp.append(0x7ffffff) # 从后向前找相邻的充电站 for j in range(i - 1, -1, -1): a_site = lst[j][0] a_time = lst[j][1] # 第i个充电站和第j个充电站的距离大于1000km则说明 【从j充电站充满电后不能直接到i充电站】 if site - a_site > 1000: break else: dp[i] = min(dp[i], dp[j] + time + 1) # 如果dp[i]没有被更新,说明不能从前面的任何一个充电站到第i个充电站,终点不可达 if dp[i] == 0x7ffffff: print(-1) sys.exit() # 因为沿途的距离是固定的,所以直接加上就行,减1是因为之前将乙地当作一个充电站,充电花费的1h要减掉 print(dp[n + 1] + int(d / 100) - 1) # 3组样例 # 1500 # 4 # 300 2 # 600 1 # 1000 0 # 1200 0 # # 800 # 2 # 300 0 # 600 0 # # 2000 # 4 # 300 2 # 600 1 # 900 0 # 1950 3
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。