算法：环形公路加油站问题

2015-01-15 • 技术文章 • 评论

现有一圆环形路，路上有n个加油站，第i个加油站储存有N[i]升容量的油，与下一个加油站之间有一定的距离g[i]，一汽车初始无油，假设该车每公里消耗1升油，请问该车从哪个加油站出发可以绕该环形路行驶一圈。

方法一：从左往右遍历，在油量和最少的位置的下一个位置出发。

1
2
3
4
5
6
7
8
9
10

int res = 0, min = N[0] - g[0], sum = min, i = 1;
while(i < n) {
    sum += N[i] - g[i];
    if(sum < min) {
        min = sum;
        res = i;
    }
    ++i;
}
return sum >= 0 ? (res + 1) % n : -1;

方法二：开辟一个长度为N的数组v，记录N[i]-g[i]。从后往前遍历数组v，如果v[i]小于零，将其与v[i-1]合并，因为此时i不可能作为起点。如果v[i]不小于零，记入sum，并记录该位置pos（有可能作为起点）。最后，如果v[0]大于等于零，说明整个路段已经没有负的v[i]。返回0即可。如果v[0]+sum>=0，有满足条件的加油站，返回pos。否则，返回-1。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

int v[n];
for(int i = 0; i < n; ++i)
    v[i] = N[i] - g[i];
int sum = 0, pos = -1;
for(int i = n-1; i > 0; --i) {
    if(v[i] >= 0) {
        sum += v[i];
        pos = i;
    } else {
        v[i-1] += v[i];
    }
}
if(v[0] >= 0) 
    return 0;
else if(v[0] + sum >= 0)
    return pos;
else 
    return -1;

方法三：开辟一个长度为2*n-1的数组v，记录N[i]-g[i]，这样就把一个环转化为一条线。使用两个指针start和end。如果[start,end]区间和小于0，令start=end+1并继续。直至找到长度为N的区间[start,end]，并且区间和大于等于0。找到返回start，找不到返回-1。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

int v[2 * n];
for (int i = 0; i < n; ++i) {
    v[i] = N[i] - g[i];
    v[i+n] = N[i] - g[i];
}
int sum = 0;
for (int start = 0, end = 0; start <= n && end < 2 * n; end++) {
    if(sum + v[end] < 0) {
        start = end + 1;
        sum = 0;
    } else {
        if(end - start == n - 1) 
            return start;
        sum += v[end];
    }
}
return -1;

以上三种解法的时间复杂度均为O(n)。对于任意一个O(n)复杂度的DP题目，必有辅助数组仅与n有关，若刨除不需要计算的量还与两个以上的量有关，则不可能做到O(n)。