Tìm trạm xăng xuất phát để hoàn thành 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 để xe hoàn thành vòng tròn (1 lít xăng = 1 đơn vị đường).

Giải bằng hàng đợi (queue) mô phỏng: thêm trạm vào hàng đợi, cập nhật xăng hiện tại. Nếu xăng < 0, loại bỏ trạm đầu cho đến khi xăng ≥ 0 hoặc hàng đợi rỗng.

Ví dụ

#include <iostream>
using namespace std;

class pump {
public:
    int petrol;
    int distance;
};

int findStartIndex(pump pumpQueue[], int n) {
    int start_point = 0, 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