查找访问C ++中所有汽油泵的第一个循环游览
假设有一个圆圈，并且该圆圈上有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