你的浏览器禁用了JavaScript, 请开启后刷新浏览器获得更好的体验!
历史记录
热门搜索
没有找到相关结果
cpcs - 诚实努力
赞同来自: 帕其维克的世界 、maybeluo 、云凌 、秋雁沙/zhh
要回复问题请先登录或注册
诚实努力
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),因为我们只需要自己加一次把和最小的位置找出来就可以了。
另外,我们其实并没有规定顺时针还有逆时针行走,所以可以分别考虑求出不同方向行驶的出发点。