Posts pythonTip 27 加油站
Post
Cancel

pythonTip 27 加油站

题目描述:

一个环形的公路上有n个加油站,编号为0,1,2,…n-1, 每个加油站加油都有一个上限,保存在列表limit中,即limit[i]为第i个加油站加油的上限, 而从第i个加油站开车开到第(i+1)%n个加油站需要cost[i]升油,cost为一个列表。 现在有一辆开始时没有油的车,要从一个加油站出发绕这个公路跑一圈回到起点。 给你整数n,列表limit和列表cost,你来判断能否完成任务。 如果能够完成任务,输出起始的加油站编号,如果有多个,输出编号最小的。 如果不能完成任务,输出-1。

示例:

输入:n = 2 limit = [1, 2] cost = [2, 2]

输出:-1

分析

对于这题目,我们首先要确定一个问题,如果从一个某一个加油站出发,如何判断可以跑完一整圈?

因为汽车的邮箱没有上限,所以每到达一个加油站的时候,就把这个加油站的所有油都带走,然后判断当前油箱里面的油是不是可以跑到下一个加油站。

现在我们可以判断 从某一个加油站出发是否可以跑完整圈。 那么我们从编号从小到大开始遍历,遇到第一个满足条件的就退出即可。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
limit += limit
cost += cost

def judge(begin):
    nums = 0
    for i in range(0, n+1):
        nums += limit[begin+i]
        if nums < cost[begin+i]:
            return False
        nums -= cost[begin+i]
    return True

res = -1
for i in range(n):
    if judge(i):
        res = i
        break

print(res)
This post is licensed under CC BY 4.0 by the author.
Trending Tags
Contents

pythonTip 26 序列判断

pythonTip 28 相同数字

Trending Tags