C ++中的最小加油站数
假设有一辆汽车，从起始位置行驶到距起始位置以东t英里的目的地。
现在，沿途有许多加油站。因此，每个加油站[i]代表加油站，该加油站位于起始位置以东的加油站[i][0]英里处，并且该加油站的加油站数为[i][1]升。
如果汽车以无限大的油箱启动，那么最初的油箱中将装有燃油。它每行驶1英里就消耗1升汽油。
当汽车到达一个加油站时，它可能会停止并加油，因此现在它将所有气体从加油站转移到汽车中。我们必须找到为到达目的地汽车必须进行的最少加油站次数？如果无法到达目的地，则返回-1。
因此，如果输入类似于Target=100，startFuel=20，stations=[10,40]，[20,30]，[30,20]，[60,40]，那么输出将为3。因此最初有10升汽油，到达第一个站后，它将传输40升天然气，所以当前有（0+40）=40升天然气，然后到达第3站，现在传输20升天然气，所以当前数量是（20+20）=40，然后到达最后一个站，取40升汽油，所以当前数量（10+40）=50，到目前为止，我们已经覆盖了60英里，所以我们必须走40英里才能到达目的地，有足够的气体可以到达目标。
为了解决这个问题，我们将遵循以下步骤-
curr：=0
排序数组st
定义优先级队列pq
i：=0，cnt：=0
curr：=curr+燃料
而curr<target，做-
从循环中出来
将st[i，1]插入pq
（将i增加1）
（将cnt增加1）
while（i<st和st[i，0]<=curr的大小），执行-
如果pq为空，则-
curr：=curr+pq的最高元素
从pq中删除元素
返回（如果curr>=目标，则为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