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