← 返回 bloomberg 的题目列表Gas Station Feasibility / Complete Circuit
类型：online_judge
Problem: Gas Station Feasibility / Complete Circuit
You are given two arrays gas and cost of the same length:
gas[i] is the amount of gas you can pick up at station i.
cost[i] is the gas needed to travel from station i to station (i+1) % n.
You may start at any station with 0 gas. At each station you first refuel, then travel to the next station.
Return:
the index of a starting station from which you can complete one full loop without the tank ever going negative, or
-1 if it is impossible.
Input
Line 1: integer n
Line 2: n integers for gas
Line 3: n integers for cost
Output
A single integer: the feasible start index or -1
Constraints
1 <= n <= 2e5
0 <= gas[i], cost[i] <= 1e9
Sample Tests (5)
input:
5
1 2 3 4 5
3 4 5 1 2
output:
3
input:
3
2 3 4
3 4 3
output:
-1
input:
1
0
0
output:
0
input:
4
5 1 2 3
4 4 1 5
output:
-1
input:
4
4 6 7 4
6 5 3 5
output:
1
Example
Input
5
1 2 3 4 5
3 4 5 1 2
Output
3