#每日一面BAT#第11题环形跑道

一个环形跑道上有若干个储油点。储油点油的总量刚好够一辆汽车走完一圈。假设汽车是均匀耗油的，并且油箱足够大，初始为空。它可以选择一个储油点为起点，装好油沿着环形跑道走下去，每到一个储油点，就可以装上那里的油。问是否可以选择这样一个的起点使得让汽车走完一圈回到起点。

3 个回复

cpcs - 诚实努力

赞同来自: 帕其维克的世界、maybeluo 、云凌、秋雁沙/zhh

答案

如果把每个储油点的油量减去到下一个储油点的耗油量当成一个变量a[i]，则我们有
a[1] + a[2] + ... + a[n] = 0 因为全部油刚好够一圈，问题是这个有正有负数。
我们假设A = a[1] + a[2] + ... + a[k - 1]是前缀的最小值，并且假设A<0,因为如果A>=0，则从第一个储油点开始走，不会出现负数，这个储油点就是解了。
我们令B=a[k] + a[k + 1] + ... + a[n], 则B = -A >= 0
我们考虑 B的每个前缀
a[k], a[k] + a[k + 1], a[k] + a[k + 1] + a[k + 2],....,B, 这些前缀必须都是非负数，因为如果前缀有一个负数的x的话，从a[1]开始的前缀和A + x < A，与A最小矛盾。
我们再继续
B + a[1], B + a[1] + a[2], ..... B + A
因为从B开始加的那部分就是从a[1]开始的前缀，我们知道A是最小的，所以这串数的最小值是A + B = 0，这就证明了从a[k]开始出发，加出来的数不会出现负数。所以k是一个解。
我们这个算法的时间复杂度是O(n)，因为我们只需要自己加一次把和最小的位置找出来就可以了。
另外，我们其实并没有规定顺时针还有逆时针行走，所以可以分别考虑求出不同方向行驶的出发点。