Giả sử có một hình tròn, và có n máy bơm xăng trên hình tròn. Chúng tôi có hai bộ dữ liệu như -
- Lượng xăng mà mỗi máy bơm xăng có
- Khoảng cách từ bơm xăng này đến bơm xăng khác
Tính điểm đầu tiên, từ đó một chiếc xe tải sẽ có thể hoàn thành vòng tròn. Giả sử với 1 lít xăng thì ô tô tải đi được 1 đơn vị quãng đường. Giả sử có bốn bơm xăng, và lượng xăng, và khoảng cách từ bơm xăng tiếp theo là [(4, 6), (6, 5), (7, 3), (4, 5)], Điểm đầu tiên mà xe tải có thể đi vòng quanh là điểm bơm xăng thứ 2. Đầu ra phải là start =1 (chỉ số của bơm tuần tra thứ hai)
Vấn đề này có thể được giải quyết một cách hiệu quả bằng cách sử dụng hàng đợi. Hàng đợi sẽ được sử dụng để lưu trữ các chuyến tham quan hiện tại. Chúng tôi sẽ lắp cây bơm xăng đầu tiên vào hàng đợi, chúng tôi sẽ cắm cây bơm xăng cho đến khi chúng tôi hoàn thành chuyến tham quan, hoặc lượng xăng hiện tại trở nên âm. Nếu số tiền trở nên âm, thì chúng tôi tiếp tục xóa các máy bơm xăng cho đến khi hết.
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;
} Đầu ra
Index of first petrol pump : 1