Số lần dừng tiếp nhiên liệu tối thiểu trong C ++

Giả sử có một chiếc ô tô di chuyển từ vị trí xuất phát đến đích cách vị trí xuất phát một dặm về phía đông.

Bây giờ dọc đường, có rất nhiều trạm xăng. Vì vậy, mỗi trạm [i] đại diện cho một trạm xăng là trạm [i] [0] dặm về phía đông so với vị trí xuất phát và trạm đó có trạm [i] [1] lít xăng.

Nếu xe khởi động với một bình xăng có kích thước vô hạn, bình xăng ban đầu sẽ có số lít nhiên liệu khởi động. Nó sử dụng 1 lít xăng trên 1 dặm mà nó lái.

Khi xe đến một trạm xăng, nó có thể dừng lại và đổ xăng, vì vậy bây giờ nó chuyển toàn bộ lượng xăng từ trạm vào xe. Chúng ta phải tìm số lần dừng tiếp nhiên liệu mà ô tô phải thực hiện để đến đích là bao nhiêu? Nếu không thể đến đích, hãy trả về -1.

Vì vậy, nếu đầu vào giống như Target =100, startFuel =20, station =[10,40], [20,30], [30,20], [60,40], thì đầu ra sẽ là 3. Vì vậy, ban đầu có 10 lít khí, sau khi đến trạm thứ nhất sẽ chuyển được 40 lít khí nên hiện tại có (0 + 40) =40 lít khí, đến trạm thứ 3 bây giờ chuyển 20 lít khí, vậy hiện số lượng là (20 + 20) =40 thì đến trạm cuối mất 40 lít xăng, như vậy số lượng hiện tại (10 + 40) =50, đến nay chúng tôi đã đi được 60 dặm, vậy chúng tôi phải đi thêm 40 dặm nữa mới đến được điểm đến, có đủ khí để tiếp cận mục tiêu.

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• curr:=0

• sắp xếp mảng st

• Xác định hàng đợi ưu tiên pq

• i:=0, cnt:=0

• curr:=curr + nhiên liệu

• trong khi curr

  • (tăng cnt lên 1)

  • while (i

    • chèn st [i, 1] vào pq

    • (tăng i lên 1)

  • nếu pq trống, thì -

    • Ra khỏi vòng lặp

  • curr:=curr + phần tử trên cùng của pq

  • xóa phần tử khỏi pq

• return (nếu curr> =target, sau đó là cnt, nếu không thì -1)

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

Ví dụ

#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));
}

Đầu vào

100, 10, {{10,40},{20,30},{30,20},{60,40}}

Đầu ra

3