视频链接
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
出发,通过加油和耗油,到达每一站时,剩余油量都是非负数,所以汽车可以绕行公路一周。
证明完毕。