环路加油站
Gas Stations on Circular Trek
题目详情
环形道路上有若干加油站。每两个相邻加油站之间的距离已知。每个加油站提供的油量刚好使得“所有油量总和 = 跑完整圈所需油量”。
证明：一定存在一个起始加油站，使得你从空油箱出发也能沿顺时针跑完一圈。
提示：归纳 / 反证。
Several gas stations on a circular trek have between them just enough gas for one car to make a complete round trip. Prove that if you start at the right station with an empty tank you shall be able to make it all the way around.
Hint
Induction
解析
经典结论：若总油量不少于总路程，则存在起点可行。
证明思路（贪心/归纳）：沿顺时针累计“油量 - 距离”的前缀和。选择使该前缀和取得最小值的下一个站作为起点，则从该站出发，任意前缀的累计差值都不为负，因此油箱不会在途中耗尽。
因此一定存在可行起点。
Original Explanation
Solution
Take N=2 gas stations. Assume their capacities are x1 and x2 (in terms of distance). Now, x1+x2 = 1. Assume y1 and y2 be clockwise distances from 1 to 2 and 2 to 1 (clockwise), y1+y2 = 1. Hence we cant have x1<y1 and x2<y2 both. Thus, let x1 >= y1. In this case we start with station 1 and complete the journey. Assume the path is possible for N=K stations, we want to prove for N = K+1 stations, using same argument as above, xi>=yi for some i, and hence reaching xi with zero fuel ensures reaching x(i+1). Thus we merge xi and x(i+1), and the problem is reduced to N=K stations, which we assumed!
Another method is to imagine having a big tank with enough gas for a round trip and enough room for going through the motions of emptying every gas station on your way. Start at any station and mind to record the amount of gasoline on reaching gas stations on your way around. At the end of the trip, when you pull into the station of departure with the original amount of gas, check your list. The station marked with the least number is the one where you want to start on an empty tank.