C++에서 모든 가솔린 펌프를 방문하는 최초의 순환 투어 찾기

원이 있고 그 원 위에 n개의 휘발유 펌프가 있다고 가정합니다. 다음과 같은 두 가지 데이터 세트가 있습니다.

• 모든 휘발유 펌프에 있는 휘발유의 양
• 한 휘발유 펌프에서 다른 휘발유 펌프까지의 거리

트럭이 원을 완성할 수 있는 첫 번째 지점을 계산합니다. 1리터 휘발유의 경우 트럭이 1단위 거리를 갈 수 있다고 가정합니다. 4개의 휘발유 펌프가 있고 휘발유의 양과 다음 휘발유 펌프까지의 거리는 [(4, 6), (6, 5), (7, 3), (4, 5)]와 같다고 가정합니다. 트럭이 순환 투어를 할 수 있는 첫 번째 지점은 2nd 휘발유 펌프입니다. 출력은 시작되어야 합니다 =1(두 번째 패트롤 펌프의 인덱스)

이 문제는 queue를 사용하여 효율적으로 해결할 수 있습니다. 대기열은 현재 투어를 저장하는 데 사용됩니다. 첫 번째 휘발유 펌프를 대기열에 삽입하고, 둘러보기를 완료하거나 현재 휘발유 양이 음수가 될 때까지 휘발유 펌프를 삽입합니다. 금액이 음수가 되면 비워질 때까지 휘발유 펌프를 계속 삭제합니다.

예시

#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