C++ 中的加油站
c++server side programmingprogramming更新于 2025/4/16 10:37:17
假设有一个圆，圆上有 n 个加油站。我们有两组数据，如 −
- 每个加油站的汽油量
- 从一个加油站到另一个加油站的距离。
计算汽车能够完成圆周的第一个点。假设 1 个单位的汽油，汽车可以行驶 1 个单位的距离。假设有四个加油站，汽油量和与下一个加油站的距离为 [(4, 6), (6, 5), (7, 3), (4, 5)]，汽车可以进行循环行驶的第一个点是第二个加油站。输出应为 start = 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
