C++での給油停止の最小数

開始位置から開始位置からtマイル東にある目的地まで移動する車があるとします。

現在、多くのガソリンスタンドがあります。したがって、各ステーション[i]は、開始位置から東にステーション[i] [0]マイルのガソリンスタンドを表し、そのステーションにはステーション[i][1]リットルのガスがあります。

車が無限のサイズのガスタンクで始動する場合、最初はstartFuelリットルの燃料が入っています。走行距離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+燃料

• 現在、<ターゲット、実行-

  • （cntを1増やします）

  • while（i

    • st [i、1]をpqに挿入します

    • （iを1増やします）

  • pqが空の場合、-

    • ループから出てきます

  • curr：=curr+pqの最上位要素

  • pqから要素を削除する

• return（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