There is a circle round, and gas stations are distributed averagely along the round, every station located in each L km, given N stations, so the total length of the road is N * L (km), and each station(numbered from 0 ~ N-1) has gas[i] gas, and given K as the gas needed per km, and the car's gas tank has infinity capacity, the problem is to find the following: - Is there a possible start station that the car can go around the road and back to the original place? if there is return it, if there is more than 1, return any of such.
- If there is no such station, return -1.
Input: vector<int> gas, int L, int K Output: int
asked
hx0 1337c0d3r ♦♦ |

### The question has been closed for the following reason "bulk close" by 1337c0d3r 25 Oct '13, 06:25

answered
Kalman |

answered
syrcx |

Below is a solution to the corresponding OJ: Starting from the first gas station, move from it till the car cannot move any more. And the stations passed won't be a valid starting station. Continue test the next gas station till find a valid one or no such a station exist.
answered
nriver |

class Solution { public:
};
answered
Junjie Qi |

answered
SPICHANOK DZ... |

answered
zhangxu |

answered
Nathan |

At each station, given the gas and cost, the net gas left when arriving next station is gas[i] - cost[i]. Each station has a net gas < 0 will not be a start station. For each station, if there is an accumulation net gas < 0, this station can't be a start station. Also, if the accumulation gas from station i to j is negative, all these stations can't be start station. (assumed that we checked it was still position before station j. If we started from any station from i to j, it will become negative after j). So we can safely loop only one pass.
answered
denny5 |