环形加油站必存在可行起点
Race Track
题目详情
一条单向环形跑道上有 个加油站（油桶）。总油量刚好够汽车跑完整圈。
汽车从空油箱开始，沿路捡油。
证明：必存在一个起点，使得从该点出发能顺利跑完整圈。
You have a one-way circular track with gas cans placed around it. The total amount of gas in all cans is just enough to travel one full lap. Your car starts with an empty tank. Show that there is a starting position on the track from which you can complete the entire circuit, picking up gas along the way.
解析
经典结论。
把每段路程的“净收益”定义为（该站提供油量 − 到下一站耗油）。沿环路计算前缀和，取前缀和达到最小值的位置的下一站作为起点，则从该起点出发任意前缀净收益都不为负，因此油箱不会中途耗尽。
所以必存在可行起点。
Original Explanation
By contradiction or inductive argument: if you assume you cannot make it starting at any point, you get a contradiction. A standard induction merges any pair of adjacent stations if the station in front had enough fuel to reach the next station. Eventually, you reduce to a single combined station or prove at least one feasible start must exist. Hence there must be a starting position that allows the full lap.