加油站圆之旅 [英] Petrol Pumps circular tour

问题描述

问题：

  

假设有一个圆。还有一些对正圆n加油站。   您将得到两个数据集。

     

  
1. 汽油的汽油泵将给予该金额
  
2. 从该汽油泵到下一个汽油泵的距离。
  

     

计算从那里一辆卡车就能完成第一点   圆

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

算法：

我开始从起点开始，我试图将左行进距离的汽油休息。如果数值为＆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:

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

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).

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