t********e
发帖数: 25 | 1 There are n petrol bunks arranged in circle. Each bunk is separated from
the rest by a certain distance. You choose some mode of travel which needs
1litre of petrol to cover 1km distance. You can't infinitely draw any
amount of petrol from each bunk as each bunk has some limited petrol only.
But you know that the sum of litres of petrol in all the bunks is equal to
the distance to be covered.
ie let P1, P2, ... Pn be n bunks arranged circularly. d1 is distance
between p1 and p2, d2 is distance b |
g*******y
发帖数: 1930 | 2 我觉得那个suggest solution有问题
我觉得这个题目是一个另外一个经典题目的隐藏变形版，什么题目呢，就是前阵子在版
上讨论过的，一个循环数组，求子数组max sum
考虑逆时针和顺时针，应该有两个循环数组
一个循环数组的元素是x[i] = p_i - d_i
另外一个循环数组的元素是x[i]' = p_i - d_(i-1)
这个题目可以等效为，在上面的循环数组中找一个起点x[k]，使得
x[k]>=0,
x[k]+x[k+1]>=0
x[k]+x[k+1]+x[k+2]>=0
...
x[k]+...x[n]+x[1]+...x[k-2]>=0
起点x[k]选在能给出Max sum的subarray的起点，是一个贪心解。 |
r**u
发帖数: 1567 | 3 agree
【在 g*******y 的大作中提到】
: 我觉得那个suggest solution有问题
: 我觉得这个题目是一个另外一个经典题目的隐藏变形版，什么题目呢，就是前阵子在版
: 上讨论过的，一个循环数组，求子数组max sum
: 考虑逆时针和顺时针，应该有两个循环数组
: 一个循环数组的元素是x[i] = p_i - d_i
: 另外一个循环数组的元素是x[i]' = p_i - d_(i-1)
: 这个题目可以等效为，在上面的循环数组中找一个起点x[k]，使得
: x[k]>=0,
: x[k]+x[k+1]>=0
: x[k]+x[k+1]+x[k+2]>=0
|
t********e
发帖数: 25 | 4 Can you give the link?
What about DP?? |
H*M
发帖数: 1268 | 5 没太看懂题.
Pi已知吗？di已知
这么说travel的距离必须要sigma(Pi)才行。大于一圈吗？必须每个P都遍历到？
汽车的油箱可以 carry as much as possible?
【在 g*******y 的大作中提到】
: 我觉得那个suggest solution有问题
: 我觉得这个题目是一个另外一个经典题目的隐藏变形版，什么题目呢，就是前阵子在版
: 上讨论过的，一个循环数组，求子数组max sum
: 考虑逆时针和顺时针，应该有两个循环数组
: 一个循环数组的元素是x[i] = p_i - d_i
: 另外一个循环数组的元素是x[i]' = p_i - d_(i-1)
: 这个题目可以等效为，在上面的循环数组中找一个起点x[k]，使得
: x[k]>=0,
: x[k]+x[k+1]>=0
: x[k]+x[k+1]+x[k+2]>=0
|
b***e
发帖数: 1419 | 6 这个有什么问题?
油够就正着走, 油不够就倒着走, 两头碰上就得.
i = 0; j = 1;
s = p[0] - d[0];
while (i != j) {
if (s >= 0) {
s += p[j] - d[j];
j = (j + 1) % n;
} else {
i = (i - 1) % n;
s += p[i] - d[i];
}
}
return i;
from
needs
only.
equal to
【在 t********e 的大作中提到】
: There are n petrol bunks arranged in circle. Each bunk is separated from
: the rest by a certain distance. You choose some mode of travel which needs
: 1litre of petrol to cover 1km distance. You can't infinitely draw any
: amount of petrol from each bunk as each bunk has some limited petrol only.
: But you know that the sum of litres of petrol in all the bunks is equal to
: the distance to be covered.
: ie let P1, P2, ... Pn be n bunks arranged circularly. d1 is distance
: between p1 and p2, d2 is distance b
|
g*******y
发帖数: 1930 | 7 题目确实不是很清楚
我把它简述一下：
n个油站排在一个圈上，每个油站的油量pi已知，油站相邻距离di已知
并且假设你的汽车有无限大的gas tank
一个简单版本的问题是：
你的汽车起始于某个油站，按逆时针(或顺时针)开车，判定能否访问所有的油站，如果
能，给出起始点。这个就直接是我前面说的解法。
难的版本的问题是:
求最大能开的距离，允许折返路线。
这种情况我觉得是先证明个引理：最多只需要变方向一次
但是接下来貌似还是比较难处理。。。
【在 H*M 的大作中提到】
: 没太看懂题.
: Pi已知吗？di已知
: 这么说travel的距离必须要sigma(Pi)才行。大于一圈吗？必须每个P都遍历到？
: 汽车的油箱可以 carry as much as possible?
|
H*M
发帖数: 1268 | 8 不是吧.他是让找从哪个可以走.
你这是判断从开始走行不行
【在 b***e 的大作中提到】
: 这个有什么问题?
: 油够就正着走, 油不够就倒着走, 两头碰上就得.
: i = 0; j = 1;
: s = p[0] - d[0];
: while (i != j) {
: if (s >= 0) {
: s += p[j] - d[j];
: j = (j + 1) % n;
: } else {
: i = (i - 1) % n;
|
H*M
发帖数: 1268 | 9 谢谢genius..这么一解释好懂多了.
【在 g*******y 的大作中提到】
: 题目确实不是很清楚
: 我把它简述一下：
: n个油站排在一个圈上，每个油站的油量pi已知，油站相邻距离di已知
: 并且假设你的汽车有无限大的gas tank
: 一个简单版本的问题是：
: 你的汽车起始于某个油站，按逆时针(或顺时针)开车，判定能否访问所有的油站，如果
: 能，给出起始点。这个就直接是我前面说的解法。
: 难的版本的问题是:
: 求最大能开的距离，允许折返路线。
: 这种情况我觉得是先证明个引理：最多只需要变方向一次
|
b***e
发帖数: 1419 | 10 那你找一组数试一下.
【在 H*M 的大作中提到】
: 不是吧.他是让找从哪个可以走.
: 你这是判断从开始走行不行
|
|
|
t********e
发帖数: 25 | 11 Is it greedy? Or is it DP?
since sum(x1<->xn) = 0.
think the array as + - + - + - + - ....
say sum(x1<->xk) is the maximum
For the maximum sum segment, there will be no sum(x1<->xi') < 0 , i' <
k,
otherwise, the maximum sum segment is sum(xi'+ 1<->xk).
OK. So there is no problem travelling in the maximum segment.
Also after the maximum sum segment, there will be no segment is smaller
than
-sum(x1<->xk). if there is one, say sum(xk+1<->xk'), k' >= k+1 and
could
be
any. Then from the end of such s |
b***e
发帖数: 1419 | 12 这个题没必要DP. 直接扫一圈就可以了：
从任意一点i(=j)出发，如果油足够往下走到下一个站，就往下走(j++)。如此往复直到
油不够。
如果有不够走到下一个j，那么看看缺了多少。 假设缺a升油，那么一个直接的结论就
是，从i可以走到下一个j当且仅当在i的时候已经有了a升油。这a升油只能是从i前面
的站省出来的。所以知道i不是第一站。所以把i往前推(i--)。如此往复，直到从i开
始油足够走到j。
往复执行如上两步，直到两个搜寻点相遇(i==j)。
这个构造性的算法同时证明了如果Sum{p} > Sum{d}, 总是有解的。
具体程序看我前面的帖子。
smaller
【在 t********e 的大作中提到】
: Is it greedy? Or is it DP?
: since sum(x1<->xn) = 0.
: think the array as + - + - + - + - ....
: say sum(x1<->xk) is the maximum
: For the maximum sum segment, there will be no sum(x1<->xi') < 0 , i' <
: k,
: otherwise, the maximum sum segment is sum(xi'+ 1<->xk).
: OK. So there is no problem travelling in the maximum segment.
: Also after the maximum sum segment, there will be no segment is smaller
: than
|
m*****f
发帖数: 1243 | 13 这题得简单版本蛮经典的， 我记得就是从头到尾加一遍油量差，小于零就reset
难版本我没懂， 既然汽车油箱无限大， 为什么要折返?
【在 g*******y 的大作中提到】
: 题目确实不是很清楚
: 我把它简述一下：
: n个油站排在一个圈上，每个油站的油量pi已知，油站相邻距离di已知
: 并且假设你的汽车有无限大的gas tank
: 一个简单版本的问题是：
: 你的汽车起始于某个油站，按逆时针(或顺时针)开车，判定能否访问所有的油站，如果
: 能，给出起始点。这个就直接是我前面说的解法。
: 难的版本的问题是:
: 求最大能开的距离，允许折返路线。
: 这种情况我觉得是先证明个引理：最多只需要变方向一次
|
b***e
发帖数: 1419 | 14 那个"难的"也不难。
显然折返没用。按我前述算法先找到一个可以开的最长路p1。这个最长路把环割开成
一条线。在线上在找一个最长可以开的路(trivial)。然后取两者里比较长的。
【在 m*****f 的大作中提到】
: 这题得简单版本蛮经典的， 我记得就是从头到尾加一遍油量差，小于零就reset
: 难版本我没懂， 既然汽车油箱无限大， 为什么要折返?
|
t********e
发帖数: 25 | 15 @Blaze
I think your explain is right. Though the DP O(n) is also OK. actually the
two concept is similar, all step by step increase. |
b***e
发帖数: 1419 | 16 Yes. My point is to show if there's a simple way to solve the problem,
don't go complicated.
the
【在 t********e 的大作中提到】
: @Blaze
: I think your explain is right. Though the DP O(n) is also OK. actually the
: two concept is similar, all step by step increase.
|
g*******y
发帖数: 1930 | 17 有需要折返的情况
例子:
p1=1, p2=10, p3=1
d12=2, d23=2, d31=9999999999
如果目标是“尽可能用光所有的油”：
方案应该是p2->p1->改变方向到p3
【在 b***e 的大作中提到】
: 那个"难的"也不难。
: 显然折返没用。按我前述算法先找到一个可以开的最长路p1。这个最长路把环割开成
: 一条线。在线上在找一个最长可以开的路(trivial)。然后取两者里比较长的。
|
g*******y
发帖数: 1930 | 18 i跟j最后不是相遇吧，而是相差1，因为只是要访问所有的油站的话，有某两个相邻油
站之间那段可以不走的。
另外，做i--的时候，假设i减小到了某个i'，这个时候你在i'->i的路上攒够了a升油。但是你如何保证i'->i'+1, i'->i'+2, ... i'->i-1这些段上的攒油量全部都是正数？
【在 b***e 的大作中提到】
: 这个题没必要DP. 直接扫一圈就可以了：
: 从任意一点i(=j)出发，如果油足够往下走到下一个站，就往下走(j++)。如此往复直到
: 油不够。
: 如果有不够走到下一个j，那么看看缺了多少。 假设缺a升油，那么一个直接的结论就
: 是，从i可以走到下一个j当且仅当在i的时候已经有了a升油。这a升油只能是从i前面
: 的站省出来的。所以知道i不是第一站。所以把i往前推(i--)。如此往复，直到从i开
: 始油足够走到j。
: 往复执行如上两步，直到两个搜寻点相遇(i==j)。
: 这个构造性的算法同时证明了如果Sum{p} > Sum{d}, 总是有解的。
: 具体程序看我前面的帖子。
|
b***e
发帖数: 1419 | 19 The goal is to find a longest path that can be traveled non-stop.
【在 g*******y 的大作中提到】
: 有需要折返的情况
: 例子:
: p1=1, p2=10, p3=1
: d12=2, d23=2, d31=9999999999
: 如果目标是“尽可能用光所有的油”：
: 方案应该是p2->p1->改变方向到p3
|
b***e
发帖数: 1419 | 20 看一下我的程序，代一组数试一试。a(in my program called s)是在不断变化的。
。但是你如何
保证i'->i'+1, i'->i'+2, ... i'->i-1这些段上的攒油量全部都是正数？
【在 g*******y 的大作中提到】
: i跟j最后不是相遇吧，而是相差1，因为只是要访问所有的油站的话，有某两个相邻油
: 站之间那段可以不走的。
: 另外，做i--的时候，假设i减小到了某个i'，这个时候你在i'->i的路上攒够了a升油。但是你如何保证i'->i'+1, i'->i'+2, ... i'->i-1这些段上的攒油量全部都是正数？
|
|
|
g*******y
发帖数: 1930 | 21 嗯，我想了下，“保证i'->i'+1, i'->i'+2, ... i'->i-1这些段上的攒油量全部都是
正数”在你的code里面是已经implicitly保证了的。
【在 b***e 的大作中提到】
: 看一下我的程序，代一组数试一试。a(in my program called s)是在不断变化的。
:
: 。但是你如何
: 保证i'->i'+1, i'->i'+2, ... i'->i-1这些段上的攒油量全部都是正数？
|
g*******y
发帖数: 1930 | 22 可能我们的理解有点不一样，我理解的是longest distance，就是耗油量，尽量访问所
有油站，但是不一定要跑遍整个圈。
【在 b***e 的大作中提到】
: The goal is to find a longest path that can be traveled non-stop.
|
b***e
发帖数: 1419 | 23 I see your point.
【在 g*******y 的大作中提到】
: 可能我们的理解有点不一样，我理解的是longest distance，就是耗油量，尽量访问所
: 有油站，但是不一定要跑遍整个圈。
|
