当前位置： 面试刷题>> 加油站(经典算法150题)
### 题目描述补充
**题目：加油站问题**
在一条笔直的公路上，有N个加油站，每个加油站有一定的油量，并且它们之间的距离是已知的。一辆汽车从起点（第一个加油站）出发，每个加油站只能加油一次（也可以不加），目标是行驶到终点（最后一个加油站）。然而，汽车的油箱容量有限，不足以一次性从起点开到终点。请设计一个算法，判断汽车是否能从起点行驶到终点，如果可以，返回最小的加油次数；如果不行，则返回-1。
### 示例
**输入**：
- 加油站数量N = 4
- 油箱容量C = 10
- 加油站油量数组：[5, 2, 3, 6]
- 加油站间距离数组：[3, 2, 1]
**解释**：
- 加油站的位置为：0, 3, 5, 6（从起点开始，单位距离）
- 加油站油量为：[5, 2, 3, 6]
- 加油站间距离为：[起点到第一个加油站3单位，第一个到第二个2单位，第二个到第三个1单位]
**输出**： 2
**解释**：
- 汽车可以在第一个加油站加5单位油，行驶到第二个加油站（剩余2单位油），然后不加油继续行驶到第三个加油站（剩余1单位油）。
- 在第三个加油站加3单位油，足够行驶到第四个加油站（终点）。
- 因此，最少需要加油2次。
### PHP 示例代码
```php
function canReachDestination($C, $stations, $distances) {
$n = count($stations);
$totalDistance = array_sum($distances);
if ($stations[0] < $distances[0]) return -1; // 起点油量不足以到第一个加油站
$dp = array_fill(0, $n + 1, $C + $stations[0]); // dp[i]表示到达第i个加油站时的最大剩余油量
$dp[0] = $C; // 起点时的油量
for ($i = 1; $i <= $n; $i++) {
$required = $distances[$i - 1]; // 到达第i个加油站所需的油量
$dp[$i] = max(0, $dp[$i - 1] - $required); // 尝试不加油到达第i个加油站
// 尝试在第i个加油站加油
if ($i < $n) {
$dp[$i + 1] = max($dp[$i + 1], $dp[$i] + $stations[$i]);
}
if ($dp[$i] < 0) return -1; // 如果到达不了第i个加油站，则无法到达终点
}
return ($dp[$n] >= $distances[$n - 1] ? $n : -1); // 检查是否足以到达终点
}
// 示例用法
$C = 10;
$stations = [5, 2, 3, 6];
$distances = [3, 2, 1];
echo canReachDestination($C, $stations, $distances); // 输出 2
```
### Python 示例代码
```python
def canReachDestination(C, stations, distances):
n = len(stations)
total_distance = sum(distances)
if stations[0] < distances[0]: return -1
dp = [C + stations[0]] + [0] * n # dp[i] 表示到达第i个加油站时的最大剩余油量
dp[0] = C
for i in range(1, n + 1):
required = distances[i - 1] if i > 0 else 0
dp[i] = max(0, dp[i - 1] - required)
if i < n:
dp[i + 1] = max(dp[i + 1], dp[i] + stations[i])
if dp[i] < 0: return -1
return n if dp[n] >= distances[n - 1] else -1
# 示例用法
C = 10
stations = [5, 2, 3, 6]
distances = [3, 2, 1]
print(canReachDestination(C, stations, distances)) # 输出 2
```
### JavaScript 示例代码
```javascript
function canReachDestination(C, stations, distances) {
const n = stations.length;
const totalDistance = distances.reduce((a, b) => a + b, 0);
if (stations[0] < distances[0]) return -1;
const dp = new Array(n + 1).fill(0);
dp[0] = C;
dp[1] = C + stations[0];
for (let i = 1; i < n; i++) {
const required = distances[i - 1];
dp[i + 1] = Math.max(0, dp[i] - required) + (i < n ? stations[i] : 0);
if (dp[i + 1] < 0) return -1;
}
return dp[n] >= distances[n - 1] ? n : -1;
}
// 示例用法
const C = 10;
const stations = [5, 2, 3, 6];
const distances = [3, 2, 1];
console.log(canReachDestination(C, stations, distances)); // 输出 2
```
以上代码均实现了题目要求的功能，并给出了适当的示例和解释。