假设有一个圆圈,并且该圆圈上有n个汽油泵。我们有两组数据,例如-
每个加油泵拥有的汽油量
一个汽油泵到另一个的距离。
计算第一个点,卡车将从该点完成圆。假设使用1升汽油,卡车可以行驶1单位的距离。假设有四个汽油泵,汽油量和到下一个汽油泵的距离为[(4,6),(6,5),(7,3),(4,5)],卡车可以绕行的第一点是第二个汽油泵。输出应该是start = 1(第二个巡检泵的索引)
使用队列可以有效地解决此问题。队列将用于存储当前巡视。我们将把第一个汽油泵插入队列,我们将插入汽油泵直到我们完成巡回演出,或者当前汽油量变为负数。如果数量变为负数,那么我们将继续删除汽油泵,直到其变空。
#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; }
输出结果
Index of first petrol pump : 1