c++ - 汽油泵循环之旅

Question

问题：

假设有一个圆圈。那个圆圈上有 n 个汽油泵。给你两组数据。

1. 汽油泵将提供的汽油量。
2. 从那个汽油泵到下一个汽油泵的距离。

计算卡车能够完成圆圈的第一个点

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

算法：

我从起点开始，我尝试添加剩余的汽油离开行驶的距离。如果值 < 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)。

Answer 2

我认为您提供的解决方案不正确。无论何时cur_ptr大于 0，您都不会更新变量end. 因此，假设如果在每个站P[i] > D[i]，循环将一直运行到无穷大。

除了一些更改之外，我相信您还需要在end = (end + 1) % N;某处添加。我已经修改了代码，它给出了正确的解决方案。

    int PPT(int[] P, int[] D, int N)
    {
        int start = 0, end = 1, cur_ptr = P[0] - D[0];
        bool none = false;

        while (start != end)
        {
            if (cur_ptr < 0)
            {
                start = (start + 1) % N;
                if (start == 0)    // all stations have been traveled but solution is not yet available
                {
                    none = true;
                    break;
                }
                end = (start + 1) % N;
                cur_ptr = P[start] - D[start];
            }
            else
            {
                end = (end + 1) % N;
                cur_ptr += P[end] - D[end];
            }
        }
        return none?-1:start;
    }