Gas station II - 未名空间MITBBS历史存档

s*r2013-10-23 07:10

1 楼

做了一道 leetcode 的 Gas station 正巧看书发现另一道 Gas Station，关心的是最
少加油次数，特此分享
题目是这样的，有 N 个加油站（给出坐标）直线排列，每个加油站最多加 B(i) 升油
。一开始车有 P 升油在原点，单位油走单位长度，需要行驶 L 长度。同样油箱也是无
限大的。问最少加油次数到达终点，或者不能走到。

s*u2013-10-23 07:10

2 楼

lz是Gas station问题迷，哈哈

m*g2013-10-23 07:10

3 楼

想不出来DP的方法。 DFS应该可以， two choices at each station, skip it or
pump gas. record the decisions and prune if next station/end point not
reachable

t*d2013-10-23 07:10

4 楼

跟那个jump game有联系么？可以联想下。

D*d2013-10-23 07:10

5 楼

这不是 Jump game 吗？

d*k2013-10-23 07:10

6 楼

題目的意思應該是從原點（0）到最後一點（n-1)，而不是像gas station要從任意點走
一圈。抛砖引玉说一个复杂度较高的DP。
f(i, p)表示位於i點，油量為p時候的解。令m = P + B(0) + B(1) + ... + B(n-1) 。
dist(i, j)表示i, j兩點間的距離。
顯然對於0 <= p <= m，有f(n-1, p) = 0
對於f(i, j), 0 <= i <= n -2, 0 <= j <= m，
若j >= dist(i, n - 1)則f(i, j) = 0
否則f(i, j) = 1 + min(f(k+1, j - dist(i, k＋1) + B(k)), k需要滿足條件
(1) i <= k <= n - 2。
(2) j >= dist(i, k)
(3) j - dist(i, k) + B(k) >= dist(k, k+1)
(4) f(k + 1, j - dist(i, k+1 ) + B(k)) >= 0
若無滿足條件的k，則f(i,j) = -1
最後返回f(0, P)。时间复杂度n * n * m。
我想如果面试可以先这么回答看看面试官的反应，实际上搜素加剪枝应该效果更好。比
如，对于每个点，预先计算从它开始走到最后一个点至少需要多少油。如果搜索时到这
个点油量已经低于最低油量，则可以跳过当前方案。应该还有很smart的剪枝。
期待楼主公布答案啊。

【在 s*****r 的大作中提到】

: 做了一道 leetcode 的 Gas station 正巧看书发现另一道 Gas Station，关心的是最
: 少加油次数，特此分享
: 题目是这样的，有 N 个加油站（给出坐标）直线排列，每个加油站最多加 B(i) 升油
: 。一开始车有 P 升油在原点，单位油走单位长度，需要行驶 L 长度。同样油箱也是无
: 限大的。问最少加油次数到达终点，或者不能走到。

f*n2013-10-23 07:10

7 楼

这道题是用优先队列解最简单。每次遇到一个station,你就赢得了B[i]的加油权利，把
这个权利放入优先队列。等你发现没油了，就从优先队列里找油最多的站来加，并将此
站取出优先队列。
这个题好像经常用在ACM入门题库里。

t*r2013-10-23 07:10

8 楼

只要油箱大小不限，没有本质区别。

【在 s*****r 的大作中提到】

: 做了一道 leetcode 的 Gas station 正巧看书发现另一道 Gas Station，关心的是最
: 少加油次数，特此分享
: 题目是这样的，有 N 个加油站（给出坐标）直线排列，每个加油站最多加 B(i) 升油
: 。一开始车有 P 升油在原点，单位油走单位长度，需要行驶 L 长度。同样油箱也是无
: 限大的。问最少加油次数到达终点，或者不能走到。

n*e2013-10-23 07:10

9 楼

这个想法好.

【在 f******n 的大作中提到】

: 这道题是用优先队列解最简单。每次遇到一个station,你就赢得了B[i]的加油权利，把
: 这个权利放入优先队列。等你发现没油了，就从优先队列里找油最多的站来加，并将此
: 站取出优先队列。
: 这个题好像经常用在ACM入门题库里。

s*r2013-10-23 07:10

10 楼

正解，此题和 jump game 还有 gas station 是完全不同的

【在 f******n 的大作中提到】

: 这道题是用优先队列解最简单。每次遇到一个station,你就赢得了B[i]的加油权利，把
: 这个权利放入优先队列。等你发现没油了，就从优先队列里找油最多的站来加，并将此
: 站取出优先队列。
: 这个题好像经常用在ACM入门题库里。

b*e2013-10-23 07:10

11 楼

如果每次到一个加油站加油前必须把油箱倒空的话，那就是jump game。
不能用heap么？因为只要知道最值，相同的B_i不用保证顺序FILO
O(nlogn)

d*n2013-10-23 07:10

12 楼

我怎么觉得跟Jump Game II是一样的，下面是jump game ii的code
// Jump Game II using Greedy Method
public static int JumpGame2(int[] array)
{
if (array == null) return 0;
int n = array.Length;
if (n == 0 || n == 1) return 0;
int maxJump = 0;
int maxPosition = 0;
int i = 0;
while(i{
maxPosition = Math.Max(maxPosition, array[i] + i);
if (maxPosition > 0) maxJump++;
if (maxPosition >= n - 1) return maxJump;
int savedI = i;
int subMaxPosition = 0;
for (int j = i + 1; j <= maxPosition; j++)
{
int temp = array[j] + j;
if (temp > subMaxPosition)
{
subMaxPosition = temp;
i = j;
}
}
if (savedI == i) return 0; // make progress in case there is
no path
}
return 0;
}

【在 s*****r 的大作中提到】

: 正解，此题和 jump game 还有 gas station 是完全不同的

b*e2013-10-23 07:10

13 楼

我第一开始也以为是，区别是你在每个index有可能有剩余。
例如
【2，1，0，0】
jump game II 不可能达到indiex 3, 这个能达到。

【在 d***n 的大作中提到】

: 我怎么觉得跟Jump Game II是一样的，下面是jump game ii的code
: // Jump Game II using Greedy Method
: public static int JumpGame2(int[] array)
: {
: if (array == null) return 0;
: int n = array.Length;
: if (n == 0 || n == 1) return 0;
: int maxJump = 0;
: int maxPosition = 0;
: int i = 0;

d*n2013-10-23 07:10

14 楼

多谢。还真是，面试中要是碰到这个基本就挂了

【在 b*******e 的大作中提到】

:
: 我第一开始也以为是，区别是你在每个index有可能有剩余。
: 例如
: 【2，1，0，0】
: jump game II 不可能达到indiex 3, 这个能达到。

s*r2013-10-23 07:10

15 楼

做了一道 leetcode 的 Gas station 正巧看书发现另一道 Gas Station，关心的是最
少加油次数，特此分享
题目是这样的，有 N 个加油站（给出坐标）直线排列，每个加油站最多加 B(i) 升油
。一开始车有 P 升油在原点，单位油走单位长度，需要行驶 L 长度。同样油箱也是无
限大的。问最少加油次数到达终点，或者不能走到。

s*u2013-10-23 07:10

16 楼

lz是Gas station问题迷，哈哈

m*g2013-10-23 07:10

17 楼

想不出来DP的方法。 DFS应该可以， two choices at each station, skip it or
pump gas. record the decisions and prune if next station/end point not
reachable

t*d2013-10-23 07:10

18 楼

跟那个jump game有联系么？可以联想下。

D*d2013-10-23 07:10

19 楼

这不是 Jump game 吗？

d*k2013-10-23 07:10

20 楼

題目的意思應該是從原點（0）到最後一點（n-1)，而不是像gas station要從任意點走
一圈。抛砖引玉说一个复杂度较高的DP。
f(i, p)表示位於i點，油量為p時候的解。令m = P + B(0) + B(1) + ... + B(n-1) 。
dist(i, j)表示i, j兩點間的距離。
顯然對於0 <= p <= m，有f(n-1, p) = 0
對於f(i, j), 0 <= i <= n -2, 0 <= j <= m，
若j >= dist(i, n - 1)則f(i, j) = 0
否則f(i, j) = -1, 若dist(i, i+1) > B(i) + j
= 1 + f(i+1, j + B(i) - dist(i, i + 1), 若 j < dist(i, i + 1)
<= j + B(i)
= min(1 + f(i+1, j + B(i) - dist(i, i + 1), f(i+1, j)), 若
dist(i, i+1) <= j
最後返回f(0, P)。时间复杂度n * m。
我想如果面试可以先这么回答看看面试官的反应，实际上搜素加剪枝应该效果更好。比
如，对于每个点，预先计算从它开始走到最后一个点至少需要多少油。如果搜索时到这
个点油量已经低于最低油量，则可以跳过当前方案。应该还有很smart的剪枝。
期待楼主公布答案啊。

【在 s*****r 的大作中提到】

: 做了一道 leetcode 的 Gas station 正巧看书发现另一道 Gas Station，关心的是最
: 少加油次数，特此分享
: 题目是这样的，有 N 个加油站（给出坐标）直线排列，每个加油站最多加 B(i) 升油
: 。一开始车有 P 升油在原点，单位油走单位长度，需要行驶 L 长度。同样油箱也是无
: 限大的。问最少加油次数到达终点，或者不能走到。

f*n2013-10-23 07:10

21 楼

这道题是用优先队列解最简单。每次遇到一个station,你就赢得了B[i]的加油权利，把
这个权利放入优先队列。等你发现没油了，就从优先队列里找油最多的站来加，并将此
站取出优先队列。
这个题好像经常用在ACM入门题库里。

t*r2013-10-23 07:10

22 楼

只要油箱大小不限，没有本质区别。

【在 s*****r 的大作中提到】

: 做了一道 leetcode 的 Gas station 正巧看书发现另一道 Gas Station，关心的是最
: 少加油次数，特此分享
: 题目是这样的，有 N 个加油站（给出坐标）直线排列，每个加油站最多加 B(i) 升油
: 。一开始车有 P 升油在原点，单位油走单位长度，需要行驶 L 长度。同样油箱也是无
: 限大的。问最少加油次数到达终点，或者不能走到。

n*e2013-10-23 07:10

23 楼

这个想法好.

【在 f******n 的大作中提到】

: 这道题是用优先队列解最简单。每次遇到一个station,你就赢得了B[i]的加油权利，把
: 这个权利放入优先队列。等你发现没油了，就从优先队列里找油最多的站来加，并将此
: 站取出优先队列。
: 这个题好像经常用在ACM入门题库里。

s*r2013-10-23 07:10

24 楼

正解，此题和 jump game 还有 gas station 是完全不同的

【在 f******n 的大作中提到】

: 这道题是用优先队列解最简单。每次遇到一个station,你就赢得了B[i]的加油权利，把
: 这个权利放入优先队列。等你发现没油了，就从优先队列里找油最多的站来加，并将此
: 站取出优先队列。
: 这个题好像经常用在ACM入门题库里。

b*e2013-10-23 07:10

25 楼

如果每次到一个加油站加油前必须把油箱倒空的话，那就是jump game。
不能用heap么？因为只要知道最值，相同的B_i不用保证顺序FILO
O(nlogn)

d*n2013-10-23 07:10

26 楼

我怎么觉得跟Jump Game II是一样的，下面是jump game ii的code
// Jump Game II using Greedy Method
public static int JumpGame2(int[] array)
{
if (array == null) return 0;
int n = array.Length;
if (n == 0 || n == 1) return 0;
int maxJump = 0;
int maxPosition = 0;
int i = 0;
while(i{
maxPosition = Math.Max(maxPosition, array[i] + i);
if (maxPosition > 0) maxJump++;
if (maxPosition >= n - 1) return maxJump;
int savedI = i;
int subMaxPosition = 0;
for (int j = i + 1; j <= maxPosition; j++)
{
int temp = array[j] + j;
if (temp > subMaxPosition)
{
subMaxPosition = temp;
i = j;
}
}
if (savedI == i) return 0; // make progress in case there is
no path
}
return 0;
}

【在 s*****r 的大作中提到】

: 正解，此题和 jump game 还有 gas station 是完全不同的

b*e2013-10-23 07:10

27 楼

我第一开始也以为是，区别是你在每个index有可能有剩余。
例如
【2，1，0，0】
jump game II 不可能达到indiex 3, 这个能达到。

【在 d***n 的大作中提到】

: 我怎么觉得跟Jump Game II是一样的，下面是jump game ii的code
: // Jump Game II using Greedy Method
: public static int JumpGame2(int[] array)
: {
: if (array == null) return 0;
: int n = array.Length;
: if (n == 0 || n == 1) return 0;
: int maxJump = 0;
: int maxPosition = 0;
: int i = 0;

d*n2013-10-23 07:10

28 楼

多谢。还真是，面试中要是碰到这个基本就挂了

【在 b*******e 的大作中提到】

:
: 我第一开始也以为是，区别是你在每个index有可能有剩余。
: 例如
: 【2，1，0，0】
: jump game II 不可能达到indiex 3, 这个能达到。

n*f2013-10-23 07:10

29 楼

维护一个大顶堆，每遇到一个station，先判断现在油量是否为负。为负就不停从取堆
顶元素加上直到变正。然后把这个station的油量加到堆里。O(nlogn)