ধরুন একটি গাড়ি আছে, যেটি স্টার্টিং পজিশন থেকে গন্তব্যে যায় যা প্রারম্ভিক অবস্থান থেকে মাইল পূর্বে।
এখন পথে, অনেক গ্যাস স্টেশন আছে. তাই প্রতিটি স্টেশন[i] একটি গ্যাস স্টেশনকে প্রতিনিধিত্ব করে যেটি শুরুর অবস্থান থেকে [i][0] মাইল পূর্বে অবস্থিত এবং সেই স্টেশনটিতে স্টেশন[i][1] লিটার গ্যাস রয়েছে।
যদি গাড়িটি অসীম আকারের গ্যাস ট্যাঙ্ক দিয়ে শুরু হয়, যেটিতে প্রাথমিকভাবে স্টার্টফুয়েল লিটার জ্বালানি থাকে। এটি প্রতি 1 মাইলে 1 লিটার গ্যাস ব্যবহার করে যা এটি চালায়৷
যখন গাড়িটি একটি গ্যাস স্টেশনে পৌঁছায়, তখন এটি থামতে পারে এবং জ্বালানি ভরতে পারে, তাই এখন এটি স্টেশন থেকে সমস্ত গ্যাস গাড়িতে স্থানান্তরিত করে। আমাদের খুঁজে বের করতে হবে যে গাড়িটিকে তার গন্তব্যে পৌঁছানোর জন্য সর্বনিম্ন সংখ্যক রিফুয়েলিং স্টপ করতে হবে? যদি গন্তব্যে পৌঁছানো অসম্ভব হয়, ফিরে আসুন -1।
সুতরাং, যদি ইনপুট টার্গেট =100, startFuel =20, স্টেশন =[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
-
(1 দ্বারা cnt বাড়ান)
-
যখন (i
-
pq
-এ st[i, 1] ঢোকান -
(i 1 দ্বারা বাড়ান)
-
-
যদি 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
