l*********y
发帖数: 142 | 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 1
litre of petrol to cover 1 km 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 liters of petrol in all the bunks is equal to the
distance to be covered.
i.e let P1, P2, ... Pn be n bunks arranged circularly. d1 is distance
between p1 and p2, d2 is distanc |
s*********t
发帖数: 1663 | 2 c[i] = p[i] - d[i]
这样题目就和求连续子序列的最大和很类似
i=0 ,j = 0
if sum [i:j] <0
i = j+1
复杂度是O(n)
代码如下
def gasStation(p, d):
n = len(p)
c = []
for i in range(n):
c.append( p[i]-d[i] )
c += c
i = 0
j = 0
total = 0
print c
while i < n:
total += c[i+j]
if total < 0:
i += j + 1
total = 0
j = 0
elif j == n:
break
else:
j += 1
return i
the
amount
you
between
【在 l*********y 的大作中提到】
: 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 1
: litre of petrol to cover 1 km 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 liters of petrol in all the bunks is equal to the
: distance to be covered.
: i.e let P1, P2, ... Pn be n bunks arranged circularly. d1 is distance
: between p1 and p2, d2 is distanc
|
f****4
发帖数: 1359 | 3 化简成求连续子序列的最大和的话，只能求出 0 ~ n 的连续子序列 例如5 ~ n-3
但如果序列 n-2,n-1,n,0,1,...,n-3 本身就是最大和的连续子序列，你的算法就找不
到n-2这个值。。。
如果对所有可能的序列开始点 i (0~n)求一次的话，复杂度还是 O(n^2)
记得类似有个题目是求循环序列（序列头尾相连）的最大和的连续子序列
谁来解一下？
【在 s*********t 的大作中提到】
: c[i] = p[i] - d[i]
: 这样题目就和求连续子序列的最大和很类似
: i=0 ,j = 0
: if sum [i:j] <0
: i = j+1
: 复杂度是O(n)
: 代码如下
: def gasStation(p, d):
: n = len(p)
: c = []
|
s*********t
发帖数: 1663 | 4 没看懂你写的
我的算法应该可以找到你说的解哦
【在 f****4 的大作中提到】
: 化简成求连续子序列的最大和的话，只能求出 0 ~ n 的连续子序列 例如5 ~ n-3
: 但如果序列 n-2,n-1,n,0,1,...,n-3 本身就是最大和的连续子序列，你的算法就找不
: 到n-2这个值。。。
: 如果对所有可能的序列开始点 i (0~n)求一次的话，复杂度还是 O(n^2)
: 记得类似有个题目是求循环序列（序列头尾相连）的最大和的连续子序列
: 谁来解一下？
|
f****4
发帖数: 1359 | 5 主要是我没看懂你的代码
你能再加点注释不？
特别是怎么循环扫描的
谢谢
【在 s*********t 的大作中提到】
: 没看懂你写的
: 我的算法应该可以找到你说的解哦
|
s*********t
发帖数: 1663 | 6 首先构造出c数组，然后把c延长一倍，就可以处理循环了
即 c += c
之后从第一个元素开始，求连续子序列的和。在子序列长度到n之前出现负数和就把这个
子序列里的元素全部跳过，从下一个开始。
我的意思是这个地方有点像求连续子序列最大和的机制，不是说两个题目完全等价
【在 f****4 的大作中提到】
: 主要是我没看懂你的代码
: 你能再加点注释不？
: 特别是怎么循环扫描的
: 谢谢
|
m*****g
发帖数: 226 | 7 确实要改一下code, 要么延长一倍，要么用%n来从头再找一遍 |
f****4
发帖数: 1359 | 8 就是这个：
“首先构造出c数组，然后把c延长一倍，就可以处理循环了
即 c += c”
我以为你的c里面就只有0~n的值，原来你是用0~n0~n来做的
多谢
这个
【在 s*********t 的大作中提到】
: 首先构造出c数组，然后把c延长一倍，就可以处理循环了
: 即 c += c
: 之后从第一个元素开始，求连续子序列的和。在子序列长度到n之前出现负数和就把这个
: 子序列里的元素全部跳过，从下一个开始。
: 我的意思是这个地方有点像求连续子序列最大和的机制，不是说两个题目完全等价
|
r****o
发帖数: 1950 | 9 就是说遍历n种情况(分别从元素1,2,...,n开始)，对吗? 如果是这样的话，复杂度还是
O(n^2)吧。
这个
【在 s*********t 的大作中提到】
: 首先构造出c数组，然后把c延长一倍，就可以处理循环了
: 即 c += c
: 之后从第一个元素开始，求连续子序列的和。在子序列长度到n之前出现负数和就把这个
: 子序列里的元素全部跳过，从下一个开始。
: 我的意思是这个地方有点像求连续子序列最大和的机制，不是说两个题目完全等价
|
s*********t
发帖数: 1663 | 10 一共遍历n个元素，o(n)
想想那个连续子序列最大和的题，只要出现负的就跳过中间所有的从下一个元素开始
【在 r****o 的大作中提到】
: 就是说遍历n种情况(分别从元素1,2,...,n开始)，对吗? 如果是这样的话，复杂度还是
: O(n^2)吧。
:
: 这个
|
|
|
r****o
发帖数: 1950 | 11 多谢，这题是不是可能有多解，只要找到一个就可以了?
一共遍历n个元素，o(n)
想想那个连续子序列最大和的题，只要出现负的就跳过中间所有的从下一个元素开始
【在 s*********t 的大作中提到】
: 一共遍历n个元素，o(n)
: 想想那个连续子序列最大和的题，只要出现负的就跳过中间所有的从下一个元素开始
|
s*********t
发帖数: 1663 | 12 应该是顺时针逆时针各一个解
【在 r****o 的大作中提到】
: 多谢，这题是不是可能有多解，只要找到一个就可以了?
:
: 一共遍历n个元素，o(n)
: 想想那个连续子序列最大和的题，只要出现负的就跳过中间所有的从下一个元素开始
|
s*********t
发帖数: 1663 | 13 也可能一堆解。。比如每一个p[i]都等于d[i]
【在 s*********t 的大作中提到】
: 应该是顺时针逆时针各一个解
|
d****j
发帖数: 293 | 14 我见过这个题，很简单，大概idea：
假设S_i为到达站i（含）后所剩的油量，可以为负数,初始值为0.
从任何一个站i=0开始，假设该站的油量是oil_i, S_i = oil_i
到达下一站S_i的油量即为 S_i = S_(i-1) + oil_i - cost_(i-1,i)
即当前车子的油量为上一站的油量数目 + 此站的油量 - 上站到此站的消耗
遍历完之后，总能找到一个最大的S_x 和x
那么，从第x站出发就肯定没问题
时间复杂度O(n)
======算法有误，更新在后面==== |
r****o
发帖数: 1950 | 15 是不是也要遍历2n, 0..n 0..n ?
【在 d****j 的大作中提到】
: 我见过这个题，很简单，大概idea：
: 假设S_i为到达站i（含）后所剩的油量，可以为负数,初始值为0.
: 从任何一个站i=0开始，假设该站的油量是oil_i, S_i = oil_i
: 到达下一站S_i的油量即为 S_i = S_(i-1) + oil_i - cost_(i-1,i)
: 即当前车子的油量为上一站的油量数目 + 此站的油量 - 上站到此站的消耗
: 遍历完之后，总能找到一个最大的S_x 和x
: 那么，从第x站出发就肯定没问题
: 时间复杂度O(n)
: ======算法有误，更新在后面====
|
Z*****Z
发帖数: 723 | 16 找最大的，也就是贪心。
为什么贪心一定行呢？
【在 d****j 的大作中提到】
: 我见过这个题，很简单，大概idea：
: 假设S_i为到达站i（含）后所剩的油量，可以为负数,初始值为0.
: 从任何一个站i=0开始，假设该站的油量是oil_i, S_i = oil_i
: 到达下一站S_i的油量即为 S_i = S_(i-1) + oil_i - cost_(i-1,i)
: 即当前车子的油量为上一站的油量数目 + 此站的油量 - 上站到此站的消耗
: 遍历完之后，总能找到一个最大的S_x 和x
: 那么，从第x站出发就肯定没问题
: 时间复杂度O(n)
: ======算法有误，更新在后面====
|
r****o
发帖数: 1950 | 17 谢谢，我还是没想明白为啥找到一个最大的S_x，然后从x出发就肯定没问题呢?
【在 d****j 的大作中提到】
: 我见过这个题，很简单，大概idea：
: 假设S_i为到达站i（含）后所剩的油量，可以为负数,初始值为0.
: 从任何一个站i=0开始，假设该站的油量是oil_i, S_i = oil_i
: 到达下一站S_i的油量即为 S_i = S_(i-1) + oil_i - cost_(i-1,i)
: 即当前车子的油量为上一站的油量数目 + 此站的油量 - 上站到此站的消耗
: 遍历完之后，总能找到一个最大的S_x 和x
: 那么，从第x站出发就肯定没问题
: 时间复杂度O(n)
: ======算法有误，更新在后面====
|
l*********y
发帖数: 142 | 18 贴一个按svncheckout的idea实现的c++. Tested.
#include
using namespace std;
int GasStation(int* d, int* g, int size)
{
int i = 0;
int* c = new int[2*size];
for (i = 0; i < 2 * size; i++) {
if (i < size) {
c[i] = g[i] - d[i];
} else {
c[i] = c[i-size];
}
}
int result = -INT_MAX;
int sum = 0;
int start = 0, j = 0;
for (i = 0; i < 2* size; i++) {
sum = sum + c[i];
if (sum >= 0) {
j++;
|
r****o
发帖数: 1950 | 19 请问，为什么sum<0时start=i+1，而不是start=start+1?
【在 l*********y 的大作中提到】
: 贴一个按svncheckout的idea实现的c++. Tested.
: #include
: using namespace std;
: int GasStation(int* d, int* g, int size)
: {
: int i = 0;
: int* c = new int[2*size];
: for (i = 0; i < 2 * size; i++) {
: if (i < size) {
: c[i] = g[i] - d[i];
|
l*****a
发帖数: 14598 | 20 处理过的这段如果是解得一部分，那么从i+1开始的n个应该包含这一段
按照你的解法就是O（n2）了
【在 r****o 的大作中提到】
: 请问，为什么sum<0时start=i+1，而不是start=start+1?
|
|
|
d****j
发帖数: 293 | 21 刚才说的方法有问题，没有仔细检查
现在重新说一下，复杂度仍然为O(n)，idea还是类似，只是细节上问题
设S_i为第i站时 目前状况下对前景的乐观程度，可以为负值，具体而言
S_i为当前所剩油量+本站油量-到达下一站的油量消耗
例如，刚开始第一站有油30升，到达下一站(第二站)需要40升，S_1=0+30-40= -10
随机取一个站a, S_a= 0 + oil_a - cost(a, a+1)
到达下一站a+1, S_(a+1) = S_a + oil_(a+1) - cost(a+1, a+2)
一直结算到最后一站，也就是a站之前的一站，此时 S_pre_a 肯定 0
选出S_i中最大的，就是能够顺利环绕一圈的站点之一（不一定唯一）
简单情况的分析结果：
如果某一站x的油很多，而到下一站消耗很少，很有可能是这个站能够成功
那么:
1.如果选择此点开始计算，那么S_x为正，很有可能大于所有的S_i，因而被选中
2.如果不幸选择此点x的下个点计算，很可能其他的S_i均为负值，而S_x=0最大
举个具体例子试试？
【在 r****o 的大作中提到】
: 谢谢，我还是没想明白为啥找到一个最大的S_x，然后从x出发就肯定没问题呢?
|
d****j
发帖数: 293 | 22 呵呵
有证明 一定存在一个站点使得汽车能顺利通过一圈
因而寻找最大的期望就一定能够行
具体的证明还要更严格的说法，俺这里捉襟见肘...
【在 Z*****Z 的大作中提到】
: 找最大的，也就是贪心。
: 为什么贪心一定行呢？
|
d*******t
发帖数: 220 | 23 人品不好，人品不好。
开玩笑的，你不怕折腾，当然应该搞了。
【在 l*****a 的大作中提到】
: 处理过的这段如果是解得一部分，那么从i+1开始的n个应该包含这一段
: 按照你的解法就是O（n2）了
|
r****o
发帖数: 1950 | 24 问问，是不是j==size的时候就可以退出循环了?
【在 l*********y 的大作中提到】
: 贴一个按svncheckout的idea实现的c++. Tested.
: #include
: using namespace std;
: int GasStation(int* d, int* g, int size)
: {
: int i = 0;
: int* c = new int[2*size];
: for (i = 0; i < 2 * size; i++) {
: if (i < size) {
: c[i] = g[i] - d[i];
|
i*****r
发帖数: 265 | 25 嗯，是的，j==size就可以退出了，如果保证题目有解的话。
【在 r****o 的大作中提到】
: 问问，是不是j==size的时候就可以退出循环了?
|
c******f
发帖数: 2144 | |
k****e
发帖数: 337 | |
h**6
发帖数: 4160 | 28 遍历一圈，然后找出达到每个加油站时油最少(或者说欠油最多)的点，然后从那里开始
，同向行驶。 |
r****o
发帖数: 1950 | 29 你说的是到达加油站的时候不加油的情况，对吗？
还有一种方法是遍历一圈，到达加油站的时候加油，然后找出每个加油站时油最多的点
，然后从那里里开始。
请问这两种方法是否等价? 还有，谁能证明这两种方法为什么正确呢?
【在 h**6 的大作中提到】
: 遍历一圈，然后找出达到每个加油站时油最少(或者说欠油最多)的点，然后从那里开始
: ，同向行驶。
|
h**6
发帖数: 4160 | 30 显然不能计算达到加油站加油之后的油量，因为需要的是成功达到下一个加油站，也就
是加油之前剩油非负。
看下图：
(2) (4)
A-----B
| |
| |
| |
| |
C
(6)
存油A2，B4，C6，距离AB5，BC3，CA4，限定顺时针行驶，那么显然应该由B出发而不是
由C出发。 |
|
|
K******g
发帖数: 1870 | 31 我怎么感觉这题很简单呢。假设有5个油桶。之间的距离是 d[5] = {7, 6, 5, 4, 3}，
油量 g[5] = {8, 2, 10, 3, 2};
1. 设一个数组a[5×2]，a[i]表示从i出发，当目前车子里累计的油量，这个值在到达
一个油桶之前和离开一个油桶之前都要check一次，不能为负数，如果为负数，就说明
不能i出发。
2. 做一个loop，从0到5×2，每一个loop，都要更新a[0]到a[i-1]的值。
比如：i = 0 a[0] = 8
i = 1, a[0] = 1(剩下的油） + 3（新加的油）， a[1] = 2
i = 2, a[0]=-2+10, a[1]=-4+10, a[2]=10,很显然，起始点0和1被淘汰
i = 3, a[2]=5+3, a[3]=3
i = 4, a[2]=4+2, a[3]=-1+2, 起始点3被淘汰
i = 5，a[2]=3+8
i = 6, a[2]=4+2
i = 7, a[2]=0, 到这个时候，因为起始点是2，恰好有一圈了， |
b***u
发帖数: 61 | 32
为什么要更新这么多？如果每个站点都可行，那总复杂度岂不是达到了O(n^2)? 其实只
要累加的起点被淘汰（比如a[0]），路上路过的点(比如a[1])也必然被淘汰 因为在到
达a[1]时 汽车里还有油。这样最后都不行 直接从a[1]出发当然更没戏。所以只要维护
一个a, 如果小于0就从零开始即可。
笔误？这个例子里新加的应该是2吧？
【在 K******g 的大作中提到】
: 我怎么感觉这题很简单呢。假设有5个油桶。之间的距离是 d[5] = {7, 6, 5, 4, 3}，
: 油量 g[5] = {8, 2, 10, 3, 2};
: 1. 设一个数组a[5×2]，a[i]表示从i出发，当目前车子里累计的油量，这个值在到达
: 一个油桶之前和离开一个油桶之前都要check一次，不能为负数，如果为负数，就说明
: 不能i出发。
: 2. 做一个loop，从0到5×2，每一个loop，都要更新a[0]到a[i-1]的值。
: 比如：i = 0 a[0] = 8
: i = 1, a[0] = 1(剩下的油） + 3（新加的油）， a[1] = 2
: i = 2, a[0]=-2+10, a[1]=-4+10, a[2]=10,很显然，起始点0和1被淘汰
: i = 3, a[2]=5+3, a[3]=3
|
g*********s
发帖数: 1782 | 33 用数学归纳法可以证明。
先证一个引理：如果循环数组的元素和为零，则存在非负的数组元素，它和数组中的下一个元素之和也
非负。
给定任意长为n的循环数组，先利用这个引理找到满足条件的元素，再把这两个元素合成一个即可。得到
的新数组长为n-1，可用归纳假设找到起点。显然这个起点也是长为n的原数组的起点。
【在 d****j 的大作中提到】
: 呵呵
: 有证明 一定存在一个站点使得汽车能顺利通过一圈
: 因而寻找最大的期望就一定能够行
: 具体的证明还要更严格的说法，俺这里捉襟见肘...
|
r********g
发帖数: 1351 | 34 这道题我看过一个证明觉得非常简洁， 就是从任意一个点开始走，计算到达每个加油
站的剩余油量
y，这样可以画一条曲线，然后总能找到一个最低点。从新开始，让最低点作为起点，
从这个起点开
始走的话，相应的曲线形状还是不变的，只是所有的点的值(也就是剩余油量)都大于0
了，相当于
移动了坐标轴。
from the
needs 1
any amount
But you
the
distance
between
such
【在 l*********y 的大作中提到】
: 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 1
: litre of petrol to cover 1 km 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 liters of petrol in all the bunks is equal to the
: distance to be covered.
: i.e let P1, P2, ... Pn be n bunks arranged circularly. d1 is distance
: between p1 and p2, d2 is distanc
|
P********l
发帖数: 452 | |
m*****s
发帖数: 19 | 36 两个指针一头一尾pstart, pend.并且一直记录从pstart到pend的和sum
向后一位一位移动pend，更新sum
如果sum小于0了，向后移动pstart直到sum〉=0，(总可以〉=0的，因为重合时就〉=0)
如果大于等于0了就停止移动pstart,再移动pend。一直这样循环，直到pend-pstart =
sizeof(pointer) * (n-1)
这时候返回pstart
the
amount
you
between
【在 l*********y 的大作中提到】
: 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 1
: litre of petrol to cover 1 km 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 liters of petrol in all the bunks is equal to the
: distance to be covered.
: i.e let P1, P2, ... Pn be n bunks arranged circularly. d1 is distance
: between p1 and p2, d2 is distanc
|
l**********g
发帖数: 426 | 37 each bunk has same fuel?
circle. Each bunk is separated from the
some mode of travel which needs 1
You can't infinitely draw any amount
some limited petrol only. But you
all the bunks is equal to the
circularly. d1 is distance
p2 and p3. dn is distance between
the travel can be started such
fuel.
【在 l*********y 的大作中提到】
: 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 1
: litre of petrol to cover 1 km 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 liters of petrol in all the bunks is equal to the
: distance to be covered.
: i.e let P1, P2, ... Pn be n bunks arranged circularly. d1 is distance
: between p1 and p2, d2 is distanc
|
