資料結構
網路
關係資料庫管理系統
作業系統
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 次檢視
廣告