一辆虚拟汽车加满油后可行驶 n n n km。旅途中有若干加油站。设计一个有效算法,指出应在哪些加油站停靠加油,使沿途加油次数最少。并证明算法能产生一个最优解。
对于给定的 n n n 和 k k k 各加油站位置,计算最少加油次数
第一行有两个正整数 n n n 和 k k k ,标识汽车加满油后可行驶 n n n km,且旅途中有 k k k 个加油站,接下来的 1 1 1 行中有 k + 1 k+1 k+1 个正整数,表示第 k k k 个加油站与第 k − 1 k-1 k−1 个加油站之间的距离。第 0 0 0 个加油站表示出发地,汽车已加满油。第 k + 1 k+1 k+1 个加油站表示目的地。
输出最少加油次数;若无法到达目的地,则输出No Solution
。
7 7
1 2 3 4 5 1 6 6
4
已知:
k
个加油站和终点,之后的每一个数字,代表从本(i
)加油站到下一个(i+1
)加油站的距离。最后一个数字(k+1
)表示从最后一个加油站到达终点站的距离。求:汽车的加油次数
到达终点站,这个虽然题目提了一嘴,但其实是可以和前边加油站在一起算的,因为从第i
个加油站到第i+1
个加油站和从第k
个加油站到达终点,过程是一样的,所以直接算在循环里即可,无需重新判断
循环判断时,只需要判断当前油量剩余距离是否可以到达下一站,即d[i]>now?
,如果可以,剩余油量减去到达下一站所需的油量即可,若不可以,则需要加满油,此时加油次数c+=1
,如果加满油之后的油量n
依然小于到下一站的距离,那么本题无解,输出No Solution
。
print('请输入汽车加满油可行驶的距离n和加油站k,中间用空格隔开:')
n, k = map(int, input().split())
print('请输入每个加油站之间的距离,空格隔开')
d = list(map(int, input().split()))
c = 0 # 初始化加油次数
now = n # 初始化当前油量
for i in range(k + 1): # 开始旅途~if now < d[i]: # 判断当前油量是否可以到达下一个加油站c += 1 # 如果无法到达,则需要加油。加油次数+1now = n # 重新初始化油量now -= d[i] # 减去到达下一站所需油量if now < 0: # 判断此时当前油量c = 'No Solution' # 当前油量为负,说明无法到达下一站,输出无解break # 不能再愉快的旅行了
print(c) # 输出结果
请输入汽车加满油可行驶的距离n和加油站k,中间用空格隔开:
7 7
请输入每个加油站之间的距离,空格隔开
1 2 3 4 5 1 6 6
4
请输入汽车加满油可行驶的距离n和加油站k,中间用空格隔开:
7 7
请输入每个加油站之间的距离,空格隔开
1 2 3 4 5 1 8 6
No Solution
程序运行正确且结果符合预期。
本文发布于:2024-02-02 13:22:37,感谢您对本站的认可!
本文链接:https://www.4u4v.net/it/170685135644083.html
版权声明:本站内容均来自互联网,仅供演示用,请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系,我们将在24小时内删除。
留言与评论(共有 0 条评论) |