Giả sử có một đường tròn, trên đó có n trạm xăng. Ta có hai tập dữ liệu:
- Lượng xăng mỗi trạm có
- Khoảng cách từ trạm này đến trạm khác.
Tính điểm xuất phát đầu tiên mà xe có thể hoàn thành vòng tròn. Giả sử 1 đơn vị xăng đi được 1 đơn vị khoảng cách. Ví dụ: 4 trạm với (xăng, khoảng cách) = [(4, 6), (6, 5), (7, 3), (4, 5)], điểm xuất phát là trạm thứ 2 (index 1).
Bài toán giải quyết hiệu quả bằng hàng đợi (queue). Queue lưu trữ chuyến đi hiện tại. Thêm trạm đầu vào queue, thêm các trạm cho đến khi hoàn thành vòng hoặc lượng xăng hiện tại âm. Nếu âm, xóa trạm cho đến khi queue rỗng.
Ví dụ
Hãy xem triển khai sau:
#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<<"Không có giải pháp"; else cout<<"Chỉ số trạm xăng đầu tiên: "<<start; }Input
[[4, 6], [6, 5], [7, 3], [4, 5]]
Output
Chỉ số trạm xăng đầu tiên: 1