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

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)。