ধরুন একটি বৃত্ত আছে, এবং বৃত্তে n গ্যাস স্টেশন আছে। আমাদের কাছে −
এর মত দুটি সেট ডেটা আছে- প্রতিটি গ্যাস স্টেশনে গ্যাসের পরিমাণ
- একটি গ্যাস স্টেশন থেকে অন্য গ্যাস স্টেশনের দূরত্ব।
প্রথম পয়েন্টটি গণনা করুন, যেখান থেকে একটি গাড়ি বৃত্তটি সম্পূর্ণ করতে সক্ষম হবে। 1 ইউনিট গ্যাসের জন্য ধরে নিন, গাড়িটি 1 ইউনিট দূরত্বে যেতে পারে। ধরুন চারটি গ্যাস স্টেশন আছে, এবং গ্যাসের পরিমাণ এবং পরবর্তী গ্যাস স্টেশন থেকে দূরত্ব হল [(4, 6), (6, 5), (7, 3), (4, 5)], প্রথম পয়েন্ট যেখান থেকে গাড়ি একটি বৃত্তাকার সফর করতে পারে তা হল ২য় গ্যাস স্টেশন। আউটপুট শুরু হওয়া উচিত =1 (দ্বিতীয় গ্যাস স্টেশনগুলির সূচক)
এই সমস্যাটি সারি ব্যবহার করে দক্ষতার সাথে সমাধান করা যেতে পারে। বর্তমান সফর সংরক্ষণ করতে সারি ব্যবহার করা হবে। আমরা প্রথম গ্যাস স্টেশনগুলিকে সারিতে ঢোকাব, আমরা গ্যাস স্টেশনগুলি সন্নিবেশ করব যতক্ষণ না, আমরা হয় ট্যুরটি সম্পূর্ণ করি, বা বর্তমান গ্যাসের পরিমাণ নেতিবাচক হয়ে যায়। যদি পরিমাণ নেতিবাচক হয়ে যায়, তাহলে আমরা গ্যাস স্টেশনগুলি মুছে ফেলতে থাকি যতক্ষণ না এটি খালি হয়ে যায়।
উদাহরণ
আসুন আরও ভালোভাবে বোঝার জন্য নিচের বাস্তবায়ন দেখি −
#include <iostream>
using namespace std;
class gas {
public:
int gas;
int distance;
};
int findStartIndex(gas stationQueue[], int n) {
int start_point = 0;
int end_point = 1;
int curr_gas = stationQueue [start_point].gas - stationQueue [start_point].distance;
while (end_point != start_point || curr_gas < 0) {
while (curr_gas < 0 && start_point != end_point) {
curr_gas -= stationQueue[start_point].gas - stationQueue [start_point].distance;
start_point = (start_point + 1) % n;
if (start_point == 0)
return -1;
}
curr_gas += stationQueue[end_point].gas - stationQueue [end_point].distance;
end_point = (end_point + 1) % n;
}
return start_point;
}
int main() {
gas gasArray[] = {{4, 6}, {6, 5}, {7, 3}, {4, 5}};
int n = sizeof(gasArray)/sizeof(gasArray [0]);
int start = findStartIndex(gasArray, n);
if(start == -1)
cout<<"No solution";
else
cout<<"Index of first gas station : "<<start;
} ইনপুট
[[4, 6], [6, 5], [7, 3], [4, 5]]
আউটপুট
Index of first gas station : 1
