C ++中的加油站

假设有一个圆圈，并且该圆圈上有n个加油站。我们有两组数据，例如-

• 每个加油站拥有的汽油量

• 一个加油站到另一个加油站的距离。

计算第一个点，汽车将从该点完成圆。假设1单位汽油，汽车可以行驶1单位距离。假设有四个加油站，且加气量和到下一个加油站的距离为[(4,6)，(6,5)，(7,3)，(4,5)]，汽车可以绕行的第一点是第二加油站。输出应该开始= 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