e*****e
发帖数: 1275 | 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 between p2 and p3. dn is distance between pn and
p1.Now find out the bunk from where the travel can be started such that your
mode of travel never runs out of fuel. | l*****g
发帖数: 685 | 2 这个提以前讨论过的
用doubly-linked list表示P1, P2, ..., Pn (--> P1 again)的环
任意点出发做traverse, 譬如从P1开始，做clockwise的计算; 如果全程走通，回到P1,
那问题就解决了。
如果只走到Pi，走不到Pi+1，那下一次就选择 Pi+1做为出发点，再做类似计算。直到
找到结果，或者回到P1.
再换成counter-clockwise, 同样地找符合条件的点。
the
amount
you
between
and
your
【在 e*****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 between p2 and p3. dn is distance between pn and
: p1.Now find out the bunk from where the travel can be started such that your
: mode of travel never runs out of fuel.
| e*****e
发帖数: 1275 | 3 我可能把这题目想复杂了。我以为你还可以从 Pi 直接去 Pj (j != i +1)
题目的意思是不是说 p1+p2+...pn = d1 + d2 +..... dn
如果是这样的话，为什么不直接从 Pmax开始呢？一开始就把油加到最满?
另外能不能让我看看以前的那个帖子？谢谢~~~~ | l*****g
发帖数: 685 | 4 the distances from Pmax to Pmax-1 and to Pmax+1 might be longer than its
feul can cover.
【在 e*****e 的大作中提到】
: 我可能把这题目想复杂了。我以为你还可以从 Pi 直接去 Pj (j != i +1)
: 题目的意思是不是说 p1+p2+...pn = d1 + d2 +..... dn
: 如果是这样的话，为什么不直接从 Pmax开始呢？一开始就把油加到最满?
: 另外能不能让我看看以前的那个帖子？谢谢~~~~
| f*******4
发帖数: 1401 | 5 "如果只走到Pi，走不到Pi+1，那下一次就选择 Pi+1做为出发点，再做类似计算。"
为什么可以skip Pi以及之前的bunks？
P1,
【在 l*****g 的大作中提到】
: 这个提以前讨论过的
: 用doubly-linked list表示P1, P2, ..., Pn (--> P1 again)的环
: 任意点出发做traverse, 譬如从P1开始，做clockwise的计算; 如果全程走通，回到P1,
: 那问题就解决了。
: 如果只走到Pi，走不到Pi+1，那下一次就选择 Pi+1做为出发点，再做类似计算。直到
: 找到结果，或者回到P1.
: 再换成counter-clockwise, 同样地找符合条件的点。
:
: the
: amount
|
|
