数据结构
网络
关系数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
时尚研究
法律研究在 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
更新于： 2019-12-17
175 次查看
广告