题解#加油站#

'''
解题思路：
1、sum(gas)<sum(cost)无解
2、行驶过程中，如gas[k]-cost[k]的累积值小于0，跳过k
3、在终点，如gas[k]-cost[k]的累积值大于等于0，即是解
'''

class Solution:
    def canCompleteCircuit(self, gas, cost):

        #print(gas)
        #print(cost)

        n = len(gas)
        pos = list(range(n))+list(range(n-1))
        #print(pos)

        if sum(gas)<sum(cost):
            return -1

        for istart in range(n):
            #print('istart=',istart)
            t = 0
            succeed = 0
            for i in range(istart,istart+n):
                k = pos[i]
                #print('k=',k)
                t += gas[k]-cost[k]
                #print('t=',t)
                if t<0:
                    break
                if i==istart+n-1 and t>=0:
                    succeed = 1
            if succeed==1:
                return istart


gas  = [1,2,3,4,5]
cost = [3,4,5,1,2]
t = Solution().canCompleteCircuit(gas,cost)
print(t)