你有一辆卡车在圆形轨道上移动,加油站在圆圈周围分开.每个站都有有限的气体.卡车上的油箱无限大.加油站之间的距离需要一定量的气体穿过.你只能向一个方向移动.
使用什么算法？你从哪个加油站开始？你可以一路走回起跑台吗？
小智 25
是的O(n)是可能的.绝对不是TSP.
设x i为站i的可用气体量减去前往下一站所需的气体量.
要求是ΣX 我 ≥0(足够的气体以完成一整圈).
考虑S i = x 1 + x 2 + ... + x i
注意,S ñ ≥0.
现在选择最小的(或者甚至是最大的将会更容易编写代码)k使得S k最小并且从它旁边的站开始.
现在对于k <Ĵ≤N,我们有气体在罐= S Ĵ - S ķ ≥0.
1个≤Ĵ≤K,我们有气体在罐= X K + 1 + ... + X Ñ + X 1 + X 2 + ... + X Ĵ = S ñ - S ķ + S Ĵ ≥0.
因此,从k + 1开始将确保在每个站处积聚足够的气体以到达下一站.
// C++ code. gas[i] is the gas at station i, cost[i] is the cost from station i to (i+1)%n
int circ(vector<int> &gas, vector<int> &cost) {
int min_S=INT_MAX, S=0, position=0;
for(int i=0;i<gas.size();i++)
{
S += gas[i] - cost[i];
if(S<min_S)
{
min_S = S;
position = (i+1) % gas.size();
}
}
if(S>=0)
return position;
else
return -1;
}
Pen*_*One 14
这是一种在O(n)时间和O(1)空间上有效的方法(而不是O(n)Aryabhatta答案的空间).
从任何一个站点开始,将其称为0站,然后前进,直到您的燃气耗尽.如果你没有用完汽油,那就完成了.否则,如果在k和k + 1站之间用完,请在站k + 1处重新开始.如果再次传递0,请记下,如果在此之后用完,则无法完成.
这样做的原因是因为如果你从车站i开始并且在车站k和k + 1之间耗尽汽油,那么如果从i和k之间的任何车站开始,你也将在车站k + 1之前耗尽汽油.
这是一个算法,给定一个数组P(汽油)和D(距离):
int position = 0;
int petrol = P[0];
int distance = D[0];
int start = 0;
while (start < n) {
while (petrol >= distance) {
petrol += P[++position % N] - distance;
distance = D[position % N];
if (position % N == start)
return start;
}
start = position;
petrol = P[start];
}
return -1;
假设cost是下一个加油站的成本数组，并且gas是可以加油的燃料数组
我们计算的区别gas[i]和cost[i]，叫diff，其中i为当前的加油站，我们在。
如果cost[i] > gas[i]（或diff < 0），这意味着我们需要有至少cost[i] - gas[i]燃料在到达车站时，我要使它的下一站，我+ 1。如果cost[i] <= gas[i]（diff >= 0），它是一个有效的起点，因为我们可以在不启动气，填补，然后前往下一个车站。最坏的情况是，我们将有一个空的坦克到达下一站。充其量，当我们达到i + 1（diff > 0）时，我们将剩下多余的燃料
实际上，我们不必从一个加油站开始，就可以成功遍历n个加油站，以了解是否存在有效的游览！只要燃料总和> =总成本，就可以进行有效游览。所以我们只需要对数组进行一次O（n）传递
更多分析：
案例1：坦克降到0以下
这只会在停下来的地方发生diff < 0。此后可能还有另一个起点，它经过一个回合经过该站后会收集足够的多余燃料。但是，我们之前通过的所有站均无济于事，因此我们无需考虑它们（请参阅案例2的说明）。
情况2：Tank当前> = 0，但是我们遇到了另一个有效的起点
我们可以放心地忽略这一点，因为：
A-B-C。如果B可以达到C，而A可以达到B，那么A可以达到C。
情况3：当前的Tank> = 0，不是有效的起点
继续进行下一个
案例4：设法达到原始起点！
好极了！
def find_starting_station(gas, cost):
sum_gas = sum_cost = tank = start = 0
for i in range(0, len(gas)):
sum_gas += gas[i]
sum_cost += cost[i]
tank += gas[i] - cost[i]
if tank < 0:
tank = 0
start = i+1
if sum_gas < sum_cost:
return -1
return start