力扣 134. 加油站

**力扣134. 加油站**

### 题目描述有 n 个加油站，位于 x 轴上，从左到右依次排列。每个加油站都有一个容量为 capacity[i] 的油箱。给定两个整数 startFuel 和 target，表示一辆车的初始油量和目标位置。

假设汽车从某个加油站开始，并且在任何时候，它都可以往前开到下一个加油站（不一定需要停下来加油）。如果汽车的油量足够，可以到达目标位置，则返回 True。否则，返回 False。

### 示例示例1：

输入：gas = [1,2,3,4,5], cost = [3,4,5,1,2], startFuel =3, target =12输出：True解释：如果我们从第一个加油站开始，汽车的油量为3。然后，我们可以往前开到下一个加油站（位置0），油量变为6。如果我们继续往前开，油量会增加到10，在位置2 加油后变为12。因此，可以到达目标位置。

示例2：

输入：gas = [5,1,2,3,4], cost = [4,4,1,5,1], startFuel =3, target =6输出：False解释：如果我们从第一个加油站开始，汽车的油量为3。然后，我们可以往前开到下一个加油站（位置0），油量变为7。如果我们继续往前开，但没有足够的油量到达目标位置。

### 解决方案#### 方法一：贪心算法

def canTravel(gas, cost, startFuel, target):
 n = len(gas)
 dp = [0] * (n +1) # dp[i] 表示从第 i 个加油站开始，到达目标位置的最小油量 for i in range(n):
 dp[i+1] = max(dp[i] - cost[i], startFuel)
 return dp[n] >= target# 测试gas = [1,2,3,4,5]
cost = [3,4,5,1,2]
startFuel =3target =12print(canTravel(gas, cost, startFuel, target)) # Truegas = [5,1,2,3,4]
cost = [4,4,1,5,1]
startFuel =3target =6print(canTravel(gas, cost, startFuel, target)) # False

def canTravel(gas, cost, startFuel, target):
 n = len(gas)
 def check(mid):
 dp = [0] * (n +1) # dp[i] 表示从第 i 个加油站开始，到达目标位置的最小油量 for i in range(n):
 dp[i+1] = max(dp[i] - cost[i], startFuel)
 return dp[n] >= target left, right =0, n * (max(gas) + min(cost))
 while left < right:
 mid = (left + right) //2 if check(mid):
 right = mid else:
 left = mid +1 return check(left)

# 测试gas = [1,2,3,4,5]
cost = [3,4,5,1,2]
startFuel =3target =12print(canTravel(gas, cost, startFuel, target)) # Truegas = [5,1,2,3,4]
cost = [4,4,1,5,1]
startFuel =3target =6print(canTravel(gas, cost, startFuel, target)) # False