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