Giả sử có một hình tròn và có n trạ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 trạm xăng đều có
- Khoảng cách từ trạm xăng này đến trạm xăng khác.
Tính điểm đầu tiên, từ đó một ô tô sẽ có thể hoàn thành vòng tròn. Giả sử cứ 1 đơn vị khí thì ô tô đi được 1 đơn vị quãng đường. Giả sử có bốn trạm xăng, và lượng xăng, và khoảng cách từ các trạm xăng tiếp theo như [(4, 6), (6, 5), (7, 3), (4, 5)], Điểm đầu tiên mà ô tô có thể đi một vòng là trạm xăng thứ 2. Đầu ra phải là start =1 (chỉ số của trạm xăng 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ẽ chèn các trạm xăng đầu tiên vào hàng đợi, chúng tôi sẽ chèn các trạ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 trạm xăng cho đến khi hết.
Ví dụ
Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -
#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;
} Đầu vào
[[4, 6], [6, 5], [7, 3], [4, 5]]
Đầu ra
Index of first gas station : 1