汽油泵圓形遊

假設有一個圓。那個圓上有幾個汽油泵。給你兩組數據。

汽油泵給予的汽油數量。

從該汽油泵到下一個汽油泵的距離。

計算從第一點卡車就能完成圓

我只是解決了這個問題。我想知道我是否正確解決了問題。

算法：

我從起點開始，我嘗試添加汽油的其餘部分向左傳播的距離。如果值爲< 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]; 
    } 
}

來源

2013-08-27 user2615516

我假設'P []'是泵的給定量，'D []'是從該泵到下一個泵的距離。你能解釋一下'cur_ptr'是什麼？以及你如何計算汽油的行駛距離？ – Thanushan

我可以假設'P []'包含用戶有足夠汽油的距離嗎？這將使得比較'D []'和'P []'更容易。 – akaHuman

[卡車在加油站周圍移動的算法可能重複]（http://stackoverflow.com/questions/2286849/algorithm-for-truck-moving-around-a-circle-of-gas-stations） –

start != end始終成立。因此，如果有解決方案，您的算法會產生無限循環。此外，我不明白，爲什麼end應該是start + 1。

這裏是另一種方法：

考慮下面的函數：

remaining petrol function

此函數計算只是在泵i到達之前剩餘的汽油。該功能可以看作如下：

remaining petrol function

功能開始於petrol = 0。你會發現這種配置是無效的，因爲在泵4時，剩餘的汽油是負值。此外，還有一個解決方案，因爲最後一個泵（也是啓動泵）的剩餘汽油是正的。

如果我們選擇不同的開始，會發生什麼？該功能的基本形狀保持不變。它剛剛移動到左側。此外，因爲該功能從petrol = 0開始，所以該功能減少C(start)。最後剩餘的燃料在這種情況下不起作用，因爲它會增加當前的汽油。

任務是找到一個start，允許所有C(i)是正面的。對於最小C(i)，在這種情況下對於start = 4顯然是這種情況。

計算函數C(i)可以迭代地完成，因此可以在線性時間內完成。您可以從0到N迭代一次。在此迭代中可以在恆定時間內（通過與當前最小值進行比較）找到最小值。因此，總體時間複雜度爲O(n)。

來源

2013-08-27 08:14:40

我不認爲您提供的解決方案是正確的。只要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; 
    }

來源

2013-08-27 07:58:03 akaHuman

汽油泵圓形遊

回答

相關問題