算法:环形公路加油站问题
现有一圆环形路,路上有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)。