資料結構
網路
關係型資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化學
生物
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究C++ 中加油站的最少次數
假設有一輛汽車，從起始位置行駛到其東邊 t 英里的目的地。
沿途有許多加油站。因此，每個 station[i] 代表一個加油站，該加油站位於起始位置東邊 station[i][0] 英里處，並且該加油站有 station[i][1] 升汽油。
如果汽車從一個無限大的油箱開始，最初油箱中有 startFuel 升汽油。它每行駛 1 英里消耗 1 升汽油。
當汽車到達一個加油站時，它可以停下來加油，因此現在它將加油站的所有汽油轉移到汽車中。我們必須找到汽車為了到達目的地必須進行的最少加油次數？如果無法到達目的地，則返回 -1。
因此，如果輸入類似於 Target = 100，startFuel = 20，stations = [10,40],[20,30],[30,20],[60,40]，則輸出將為 3。最初有 10 升汽油，到達第一個加油站後，它將轉移 40 升汽油，因此目前有 (0 + 40) = 40 升汽油，然後到達第三個加油站，現在轉移 20 升汽油，因此當前數量為 (20+20) = 40，然後到達最後一個加油站，獲取 40 升汽油，因此當前數量 (10 + 40) = 50，到目前為止，我們已經行駛了 60 英里，因此我們還需要行駛 40 英里才能到達目的地，有足夠的汽油到達目標。
為了解決這個問題，我們將遵循以下步驟 -
curr := 0
對陣列 st 進行排序
定義優先順序佇列 pq
i := 0, cnt := 0
curr := curr + fuel
當 curr < target 時，執行 -
(將 cnt 增加 1)
當 (i < st 的大小且 st[i, 0] <= curr) 時，執行 -
將 st[i, 1] 插入 pq
(將 i 增加 1)
如果 pq 為空，則 -
退出迴圈
curr := curr + pq 的頂部元素
從 pq 中刪除元素
返回 (如果 curr >= target，則返回 cnt，否則返回 -1)
讓我們看看以下實現以更好地理解 -
示例
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int minRefuelStops(int target, int fuel, vector<vector<int>> &st) {
int curr = 0;
sort(st.begin(), st.end());
priority_queue<int> pq;
int i = 0;
int cnt = 0;
curr += fuel;
while (curr < target) {
cnt++;
while (i < st.size() && st[i][0] <= curr) {
pq.push(st[i][1]);
i++;
}
if (pq.empty())
break;
curr += pq.top();
pq.pop();
}
return curr >= target ? cnt : -1;
}
};
main(){
Solution ob;
vector<vector<int>> v = {{10,40},{20,30},{30,20},{60,40}};
cout << (ob.minRefuelStops(100, 10, v));
}輸入
100, 10, {{10,40},{20,30},{30,20},{60,40}}輸出
3
487 次瀏覽
