P196. 加油站

视频链接

https://algocasts.io/episodes/AEpoBEGQ

推论证明

推论:如果加油站的油量之和,大于等于消耗的油量之和,那么肯定存在一个出发点,可以绕行公路一周。

证明:加油站的油量数组是 gas,耗油数组是 cost。假设到达下标 i 时,以下前缀和达到最小值

sum(i) = gas[0]-cost[0] + gas[1]-cost[1] +...+ gas[i]-cost[i]

其中,sum(i) 表示前缀和,同理我们有以下等式:

sum(i+1) = gas[0]-cost[0] +...+ gas[i]-cost[i] + gas[i+1]-cost[i+1]

上面两个等式相减,得到:

sum(i+1) - sum(i) = gas[i+1] - cost[i+1]

由于,sum(i) 是最小的前缀和,因此我们有以下不等式:

sum(i+1) >= sum(i)
sum(i+2) >= sum(i)
...
sum(n-1) >= sum(i)

对于以上所有不等式,把 sum(i) 移到左边,并将相同的部分抵消后,得到:

// 【不等式组 (1)】
gas[i+1]-cost[i+1] >= 0
gas[i+1]-cost[i+1] + gas[i+2]-cost[i+2] >= 0
...
gas[i+1]-cost[i+1] +...+ gas[n-1]-cost[n-1] >= 0

同理,对于 [0, i] 区间内的任意下标 j(0 <= j <= i),有以下不等式:

sum(j) >= sum(i)

不等式左右两边展开,得到:

gas[0]-cost[0] + gas[1]-cost[1] +...+ gas[j]-cost[j] >=
gas[0]-cost[0] + gas[1]-cost[1] +...+ gas[i]-cost[i]

左右两边都加上 gas[i+1]-cost[i+1] +...+ gas[n-1]-cost[n-1],得到:

gas[0]-cost[0] +...+ gas[j]-cost[j] + gas[i+1]-cost[i+1] +...+ gas[n-1]-cost[n-1]
>=
gas[0]-cost[0] +...+ gas[i]-cost[i] + gas[i+1]-cost[i+1] +...+ gas[n-1]-cost[n-1]

已知,加油站的油量之和,大于等于消耗的油量之和(这是给我们的条件),于是有:

// 【不等式组 (2)】
gas[0]-cost[0] +...+ gas[j]-cost[j] + gas[i+1]-cost[i+1] +...+ gas[n-1]-cost[n-1]
>=
gas[0]-cost[0] +...+ gas[i]-cost[i] + gas[i+1]-cost[i+1] +...+ gas[n-1]-cost[n-1]
>= 0

结合【不等式组 (1)】和【不等式组 (2)】,我们得到以下一系列不等式(0 <= j <= i):

gas[i+1]-cost[i+1] >= 0
gas[i+1]-cost[i+1] + gas[i+2]-cost[i+2] >= 0
...
gas[i+1]-cost[i+1] +...+ gas[n-1]-cost[n-1] >= 0
...
gas[i+1]-cost[i+1] +...+ gas[n-1]-cost[n-1] + gas[0]-cost[0] +...+ gas[j]-cost[j] >= 0

根据以上不等式可以知道,如果汽车从 i+1 出发,通过加油和耗油,到达每一站时,剩余油量都是非负数,所以汽车可以绕行公路一周。

证明完毕。

参考链接:
https://leetcode.com/problems/gas-station/discuss/42572/Proof-of-%22if-total-gas-is-greater-than-total-cost-there-is-a-solution%22.-C++