c++ - 汽油泵循环游

Question

问题:

Suppose there is a circle. There are n petrol pumps on that circle. You are given two sets of data.

1. The amount of petrol that petrol pump will give.
2. Distance from that petrol pump to the next petrol pump.

Calculate the first point from where a truck will be able to complete the circle

我刚刚解决了这个问题。我想知道我是否正确解决了问题。

算法:

我从起点开始，并尝试添加剩余的汽油以行进该距离。如果值 < 0 并且如果我们再次开始，则不存在解决方案。否则继续循环直到你到达终点。结束总是开始 + 1；我也知道算法 O(n)。有人也可以使用一个好的逻辑来解释它的 O(n) 是如何实现的吗？

int PPT(int P[], int D[], int N)
{

   int start = 0, end = 1, cur_ptr = P[0] - D[0], i = start;

   while(start != end)
   {

      if(cur_ptr < 0)
      {
         start = (i + 1) % N;
         end = (start + 1) % N;
         cur_ptr = 0;
         if(start == 0) return -1; // if start again becomes 0 then no solution exists

      } 
      i = (i + 1) % N;

      cur_ptr += P[i] - D[i];
   }
}

Answer 1

start != end 始终成立。因此，如果有解决方案，您的算法会产生无限循环。此外，我不明白，为什么 end 应该是 start + 1。

这是另一种方法:

考虑以下函数:

此函数计算刚好到达泵 i 之前的剩余汽油。该函数可以可视化如下:

函数从 petrol = 0 开始。您会看到此配置无效，因为在泵 4 处剩余的汽油为负。此外，还有一个解决方案，因为最后一个泵(再次启动泵)的剩余汽油为正。

如果我们选择不同的开始会怎样？函数的基本形状保持不变。它只是移到了左边。此外，因为函数从 petrol = 0 开始，所以函数减少了 C(start)。最后剩余的燃料在这种情况下不起作用，因为它会增加当前的汽油。

任务是找到一个start，让所有的C(i)都为正。这显然是最小 C(i) 的情况，在本例中为 start = 4。

计算函数 C(i) 可以迭代完成，因此可以在线性时间内完成。您从 0 到 N 迭代一次。可以在恒定时间内(通过与当前最小值进行比较)在此迭代期间找到最小值。因此，整体时间复杂度为O(n)。