สมมติว่ามีวงกลมและมีปั๊มน้ำมัน n แห่งบนวงกลม เรามีข้อมูลสองชุดเช่น −
- ปริมาณน้ำมันที่สถานีบริการน้ำมันทุกแห่งมี
- ระยะทางจากสถานีบริการน้ำมันแห่งหนึ่งไปยังอีกสถานีหนึ่ง
คำนวณจุดแรกจากตำแหน่งที่รถจะวิ่งรอบวงกลมได้ สมมุติว่าน้ำมัน 1 หน่วย รถสามารถวิ่งได้ 1 หน่วย สมมติว่ามีปั๊มน้ำมันสี่แห่ง และปริมาณน้ำมัน และระยะทางจากสถานีบริการน้ำมันถัดไปเท่ากับ [(4, 6), (6, 5), (7, 3), (4, 5)], จุดแรกที่รถสามารถวิ่งวนได้คือปั๊มน้ำมันแห่งที่ 2 เอาต์พุตควรเริ่มต้น =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
