加油站圆之旅

问题描述

问题：

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

算法：

我开始从起点开始，我试图将左行进距离的汽油休息。如果数值为＆lt; 0;而当我们到达重新开始，然后无解的存在。否则继续循环，直到你到达终点。最终总是启动+ 1;我也知道算法为O（n）。能有一个人还解释了使用一个很好的逻辑是如何的为O（n）。

  INT PPT（INT P []，INT D []，INT N）
{

   INT开始= 0，结束= 1，cur_ptr = P [0]  -  D [0]，I =开始;

   同时（开始！=结束）
   {

      如果（cur_ptr℃，）
      {
         开始=第（i + 1）％N;
         结束=（启动+ 1）％N;
         cur_ptr = 0;
         如果（开始== 0）返回-1; //如果启动再次成为0，那么无解

      }
      I =（I + 1）％N;

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

解决方案

启动！=结束总是成立。因此，你的算法产生无限循环，如果有一个解决方案。此外，我不明白，为什么结束应启动+ 1 。

下面是另一种方法：

考虑下面的函数：

此功能计算剩余的汽油刚刚到达泵我之前。该功能可以被可视如下：

该功能开始于汽油= 0 。你看到，此配置是无效的，因为在泵4剩余汽油为负。此外，有一个解决方案，因为在最后的泵（再次启动泵）剩余汽油是阳性

会发生什么，如果我们选择一个不同的开始？该函数的基本形状保持不变。这只是向左移动。此外，因为函数开始于汽油= 0 ，功能下降 C（开始）。在结束时剩余燃料不会在这种情况下发挥作用，因为这将增加电流汽油

的任务是找到一个启动，允许所有的 C（I）是积极的。这显然​​是最小的 C（I），在这种情况下，为开始= 4 的情况。

计算功能 C（I）可以反复做，因此，在线性时间。您一次迭代从0到N最低可这个迭代在固定时间过程中发现（通过与目前最低的比较）。因此，总的时间复杂度为 O（N）。

Problem:

I just solved the problem. I want to know if I solved the problem correctly.

Algorithm:

I started from starting point and I tried adding rest of the petrol left travelling the distance. if value is < 0 and if we reach start again then no solution exists. otherwise keep looping till you reach the end. End is always start + 1; Also I know the algorithm O(n). Can some one also explain using a good logic how its 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];
   }
}

解决方案

start != end always holds. Therefore, your algorithm produces an infinite loop if there is a solution. Furthermore, I don't understand, why end should be start + 1.

Here is another approach:

Consider the following function:

This function calculates the remaining petrol just before arriving at pump i. The function can be visualized as follows:

The function starts at petrol = 0. You see that this configuration is not valid, because at pump 4 the remaining petrol is negative. Furthermore, there is a solution, because the remaining petrol at the last pump (again the start pump) is positive.

What happens, if we choose a different start? The basic shape of the function remains the same. It is just moved to the left. Furthermore, because the function starts at petrol = 0, the function is decreased by C(start). The remaining fuel at the end does not play a role in this case, because it would increase the current petrol.

The task is to find a start that allows all C(i) to be positive. This is obviously the case for the minimal C(i), in this case for start = 4.

Calculating the function C(i) can be done iteratively, and therefore, in linear time. You iterate once from 0 to N. The minimum can be found during this iteration in constant time (by comparing with the current minimum). Therefore, the overall time complexity is O(n).

这篇关于加油站圆之旅的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！