← 返回 waymo 的题目列表Minimum Number of Refueling Stops
类型：online_judge
Problem: Minimum Number of Refueling Stops
A car starts at position 0 and needs to reach position target. It initially has startFuel liters of fuel. The car consumes 1 liter of fuel per unit of distance traveled.
There are several gas stations along the route. stations[i] = [position_i, fuel_i] means the i-th station is located at distance position_i from the start and can provide up to fuel_i liters of fuel.
When the car reaches a gas station, it may choose whether to refuel. If it refuels, it takes all the fuel from that station. The fuel tank has unlimited capacity.
Return the minimum number of refueling stops needed to reach the target. If it is impossible, return -1.
Input Format
target startFuel
n
position_1 fuel_1
position_2 fuel_2
...
position_n fuel_n
target: target position.
startFuel: initial amount of fuel.
n: number of gas stations.
The next n lines contain each station's position and fuel amount.
Stations are given in strictly increasing order of position.
Output Format
min_stops
Print the minimum number of stops required to reach the target, or -1 if impossible.
Constraints
1 <= target, startFuel <= 10^9
0 <= n <= 500
0 < position_i < target
1 <= fuel_i <= 10^9
position_i is strictly increasing
Example 1
Input:
1 1
0
Output:
0
Example 2
Input:
100 10
4
10 60
20 30
30 30
60 40
Output:
2
Example
Input
1 1
0
Output
0