C++のすべてのガソリンポンプを訪問する最初の循環ツアーを見つけます

円があり、円上にn個のガソリンポンプがあるとします。 -

• すべてのガソリンポンプが持つガソリンの量
• あるガソリンポンプから別のガソリンポンプまでの距離

トラックが円を完成できる最初のポイントを計算します。 1リットルのガソリンの場合、トラックは1単位の距離を移動できます。ガソリンポンプが4つあり、ガソリンの量があり、次のガソリンポンプからの距離が[（4、6）、（6、5）、（7、3）、（4、5）]のようになっているとします。トラックが循環ツアーを行うことができる最初のポイントは、2番目のガソリンポンプです。出力はstart=1（2番目のパトロールポンプのインデックス）である必要があります

この問題は、キューを使用して効率的に解決できます。キューは、現在のツアーを保存するために使用されます。最初のガソリンポンプをキューに挿入し、ツアーを完了するか、現在のガソリン量がマイナスになるまでガソリンポンプを挿入します。量がマイナスになった場合は、空になるまでガソリンポンプを削除し続けます。

例

#include <iostream>
using namespace std;
class pump {
   public:
      int petrol;
      int distance;
};
int findStartIndex(pump pumpQueue[], int n) {
   int start_point = 0;
   int end_point = 1;
   int curr_petrol = pumpQueue[start_point].petrol - pumpQueue[start_point].distance;
   while (end_point != start_point || curr_petrol < 0) {
      while (curr_petrol < 0 && start_point != end_point) {
         curr_petrol -= pumpQueue[start_point].petrol - pumpQueue[start_point].distance;
         start_point = (start_point + 1) % n;
         if (start_point == 0)
            return -1;
      }
      curr_petrol += pumpQueue[end_point].petrol - pumpQueue[end_point].distance;
      end_point = (end_point + 1) % n;
   }
   return start_point;
}
int main() {
   pump PumpArray[] = {{4, 6}, {6, 5}, {7, 3}, {4, 5}};
   int n = sizeof(PumpArray)/sizeof(PumpArray[0]);
   int start = findStartIndex(PumpArray, n);
   if(start == -1)
      cout<<"No solution";
   else
      cout<<"Index of first petrol pump : "<<start;
}

出力

Index of first petrol pump : 1