원이 있고 그 원 위에 n개의 주유소가 있다고 가정합니다. 다음과 같은 두 가지 데이터 세트가 있습니다.
- 모든 주유소의 주유량
- 한 주유소에서 다른 주유소까지의 거리
자동차가 원을 완성할 수 있는 첫 번째 점을 계산합니다. 1단위의 휘발유로 자동차는 1단위의 거리를 갈 수 있습니다. 4개의 주유소가 있고 주유소의 양과 다음 주유소까지의 거리는 [(4, 6), (6, 5), (7, 3), (4, 5)]와 같으며, 자동차가 순환할 수 있는 첫 번째 지점은 두 번째 주유소입니다. 출력 시작 =1(두 번째 주유소 인덱스)
이 문제는 큐를 사용하여 효율적으로 해결할 수 있습니다. 대기열은 현재 투어를 저장하는 데 사용됩니다. 첫 번째 주유소를 대기열에 삽입하고, 둘러보기를 완료하거나 현재 주유량이 음수가 될 때까지 주유소를 삽입합니다. 금액이 마이너스가 되면 비어있을 때까지 주유소를 계속 삭제합니다.
예시
더 나은 이해를 위해 다음 구현을 살펴보겠습니다. −
#include <iostream>
using namespace std;
class gas {
public:
int gas;
int distance;
};
int findStartIndex(gas stationQueue[], int n) {
int start_point = 0;
int end_point = 1;
int curr_gas = stationQueue [start_point].gas - stationQueue [start_point].distance;
while (end_point != start_point || curr_gas < 0) {
while (curr_gas < 0 && start_point != end_point) {
curr_gas -= stationQueue[start_point].gas - stationQueue [start_point].distance;
start_point = (start_point + 1) % n;
if (start_point == 0)
return -1;
}
curr_gas += stationQueue[end_point].gas - stationQueue [end_point].distance;
end_point = (end_point + 1) % n;
}
return start_point;
}
int main() {
gas gasArray[] = {{4, 6}, {6, 5}, {7, 3}, {4, 5}};
int n = sizeof(gasArray)/sizeof(gasArray [0]);
int start = findStartIndex(gasArray, n);
if(start == -1)
cout<<"No solution";
else
cout<<"Index of first gas station : "<<start;
} 입력
[[4, 6], [6, 5], [7, 3], [4, 5]]
출력
Index of first gas station : 1