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