最大子阵变体

Question

问题是，有一个圆形轨道，包含燃料坑，在不规则的间隔。从所有的坑一起可以得到的燃料总量仅仅足以绕着赛道旅行，并完成你开始的地方。给定线路周长、每个燃料坑位置的列表以及它们所包含的燃料量，找到轨道上的最佳起点，这样你就永远不会耗尽燃料并完成整个电路。

样本输入

(location, fuel)

(0/100, 6)
(2,16)
(18,1)
(30,45)
(84,5)
(92,27)

电路长度- 100，总燃料-100

Answer 1

JavaScript 140个字符

对于第一个解决方案，我假定燃料坑是按轨道周围位置的顺序和形式提供的：

var fuelPitInfo = [
    {
       location: 2,//The location from some point on the track
       fuelDistance: 1//The distance you can travel with the fuel from this stop
    },
    ..
]

因此，用于计算工作开始位置的潜在非代码化JavaScript函数如下(试验小提琴)：

function calculateStartingLocation(trackLength, fuelPitInfo) {
    for(i=0;;i++){
        var fuelPit = fuelPitInfo[i];
        var remainingFuelDistance = fuelPit.fuelDistance;
        for(j=i+1;;j++){
            var nextFuelPit = fuelPitInfo[j = j % fuelPitInfo.length];
            if (i == j) return fuelPitInfo[i].location;
            remainingFuelDistance -= (nextFuelPit.location - fuelPit.location + trackLength) % trackLength;
            if (remainingFuelDistance < 0) break;
            remainingFuelDistance += nextFuelPit.fuelDistance;
            fuelPit = nextFuelPit;
        }
    }
}

代码黄金函数版本(140个字符)如下(假设location被l替换，fuelDistance在提供的fuelPitInfo对象中替换为d ) (试验小提琴)：

function a(b,c){for(i=0;e=c[i],f=e.d;i++){for(j=i+1;g=c[j=j%c.length];){if(i==j++)return c[i].l;f-=(g.l-e.l+b)%b;if(f<0)break;f+=g.d,e=g;}}}

Answer 2

D (98个字符)

输入是一个int数组，如果没有燃料，则输入的燃料数量为0。

int f(int[] a){
    for(int s,r=-1,i=0;;i++){
        if(r+a.length==i)
            return r;
        if(--s<0){
            r=i;s=0;
        }
        s+=a[i%$];
    }
}

我从索引0开始使用0燃料，每当s降到0以下，我就把这个点设置为我的新起点，并将s重置为0。

如果有一个解决方案，你将永远在O(n)时间或循环中找到它。

Answer 3

Python，183

import sys
f=[map(int,_.split()) for _ in open(sys.argv[1])]
l=len(f)
s=[]
for i in range(l):
\tu,d=zip(*(f[i:]+f[:i]))
\tif all(sum(u[:j])<sum(d[:j])for j in range(l+1)):s+=[i]
print s

该程序以N行文件的形式输入，其中N是燃料库的数目。每一行包含整数A和B，其中A是油库的燃料量，B是到下一个燃料库的距离。示例：

7 5
6 7
4 3

输出是包含有效起点的燃料库索引的列表的字符串表示形式。在这种情况下，它的产出是：

[0, 2]

这意味着无论是从燃料库0开始，还是从燃料库2开始，车辆都可以绕着圆圈行驶。