Tìm trạm xăng đầu tiên để đi vòng tròn trong C++

Cho n trạm xăng trên vòng tròn, mỗi trạm có lượng xăng và khoảng cách đến trạm tiếp. Tìm trạm xuất phát để đi hết vòng. Ví dụ [(4,6),(6,5),(7,3),(4,5)] → trạm 2 (chỉ số 1).

Dùng hàng đợi: giữ trạm bắt đầu và kết thúc, tổng xăng hiện tại. Nếu âm thì loại bỏ trạm bắt đầu cho đến khi không âm.

Ví dụ

#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; }

Kết quả

Index of first petrol pump : 1