ধরুন একটি বৃত্ত আছে, এবং বৃত্তের উপর n পেট্রোল পাম্প আছে। আমাদের কাছে −
এর মত দুটি সেট ডেটা আছে- প্রতিটি পেট্রোল পাম্পে যে পরিমাণ পেট্রোল আছে
- এক পেট্রোল পাম্প থেকে অন্য পেট্রোল পাম্পের দূরত্ব।
প্রথম পয়েন্টটি গণনা করুন, যেখান থেকে একটি ট্রাক বৃত্তটি সম্পূর্ণ করতে সক্ষম হবে। অনুমান করুন 1 লিটার পেট্রোলের জন্য, ট্রাকটি 1 ইউনিট দূরত্বে যেতে পারে। ধরুন চারটি পেট্রোল পাম্প আছে, এবং পেট্রোলের পরিমাণ এবং পরবর্তী পেট্রোল পাম্প থেকে দূরত্ব [(4, 6), (6, 5), (7, 3), (4, 5)], প্রথম পয়েন্ট যেখান থেকে ট্রাক একটি বৃত্তাকার ভ্রমণ করতে পারে তা হল ২য় পেট্রোল পাম্প। আউটপুট স্টার্ট =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
