1

問題：

円があるとします。その円には n 個のガソリン ポンプがあります。2 セットのデータが与えられます。

  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];
   }
}
4

2 に答える 2

7

start != end常に保持します。したがって、解がある場合、アルゴリズムは無限ループを生成します。さらに、私は理解していませendんstart + 1。

別のアプローチを次に示します。

次の関数を検討してください。

残りのガソリン機能

この関数は、ポンプに到達する直前のガソリン残量を計算しますi。関数は次のように視覚化できます。

残りのガソリン機能

関数は から始まりpetrol = 0ます。ポンプ 4 で残りのガソリンが負であるため、この構成は有効ではないことがわかります。さらに、最後のポンプ (再び開始ポンプ) の残りのガソリンがプラスであるため、解決策があります。

別の開始を選択するとどうなりますか? 関数の基本的な形状は変わりません。左に移動しただけです。さらに、関数は から始まるため、petrol = 0関数は だけ減少しC(start)ます。最後の残りの燃料は、現在のガソリンを増加させるため、この場合は役割を果たしません。

タスクは、startすべてC(i)がポジティブになることを可能にする a を見つけることです。これは明らかに最小C(i)の 、この場合は の場合ですstart = 4。

関数の計算はC(i)反復的に実行できるため、線形時間で実行できます。0 から N まで 1 回反復します。最小値は、この反復中に一定時間で見つけることができます (現在の最小値と比較することによって)。したがって、全体の時間計算量はO(n)です。

于 2013-08-27T08:14:40.010 に答える
0

あなたが提供する解決策は正しいとは思いません。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-27T07:58:03.083 に答える