ধারণা
0 থেকে N-1 পর্যন্ত N নম্বর দেওয়া শহরগুলির প্রদত্ত সংখ্যা এবং যে শহরগুলিতে স্টেশনগুলি অবস্থিত, আমাদের কাজ হল যে কোনও শহর এবং তার নিকটতম স্টেশনের মধ্যে সর্বাধিক দূরত্ব নির্ধারণ করা। এটা উল্লেখ করা উচিত যে স্টেশন সহ শহরগুলি যে কোনও ক্রমে দেওয়া যেতে পারে।
ইনপুট
numOfCities = 6, stations = [2, 4]
আউটপুট
2
ইনপুট
numOfCities = 6, stations = [4]
আউটপুট
4
-
নীচের চিত্রটি 6টি শহর এবং সবুজ রঙ দিয়ে হাইলাইট করা স্টেশন সহ শহরগুলি সম্বলিত প্রথম উদাহরণ নির্দেশ করে৷ সুতরাং, এই ক্ষেত্রে, এর নিকটতম স্টেশনগুলি থেকে দূরবর্তী শহরগুলি 2 এর দূরত্বে 0। তাই সর্বাধিক দূরত্ব হল 1।
-
দ্বিতীয় উদাহরণে, তার নিকটতম স্টেশন থেকে দূরতম শহরটি হল 0 যা 4 দূরত্বে। তাই সর্বাধিক দূরত্ব হল 4।
পদ্ধতি
এখানে, এই সমস্যার তিনটি সম্ভাব্য কেস আছে −
-
প্রথম কেস নির্দেশ করে কখন সবচেয়ে দূরবর্তী শহর দুটি স্টেশনের মধ্যে।
-
দ্বিতীয় ক্ষেত্রে নির্দেশ করে যখন সবচেয়ে দূরবর্তী শহরটি প্রথম স্টেশনের বাম দিকে।
-
শেষ কেস নির্দেশ করে যখন সবচেয়ে দূরবর্তী শহরটি শেষ স্টেশনের ডানদিকে থাকে৷
৷
উপরের সমস্যাটি সমাধান করার জন্য নিম্নলিখিত অ্যালগরিদম প্রয়োগ করা হয়েছে -
-
আমরা False দিয়ে N (শহরের সংখ্যা) আকারের একটি বুলিয়ান অ্যারে শুরু করি। তারপরে স্টেশন সহ শহরের মানগুলিকে সত্য হিসাবে চিহ্নিত করুন
-
এরপরে আমরা 0 দিয়ে একটি ভেরিয়েবল ডিস্ট ইনিশিয়ালাইজ করি। আমাদের আরেকটি ভ্যারিয়েবল ম্যাক্সডিস্ট ইনিশিয়ালাইজ করতে হবে যার মানের সাথে স্টেশনের প্রথম সিটির সমান (দ্বিতীয় ক্ষেত্রে ব্যবহৃত হয়)।
-
একের পর এক সমস্ত শহরের মধ্যে দিয়ে লুপ করা শুরু করুন৷
৷ -
এটি লক্ষ্য করা গেছে যে যদি বর্তমান শহরের একটি স্টেশন থাকে, এবং তারপর সর্বাধিক (dist+1)//2 এবং maxDist-এ maxDist (প্রথম ক্ষেত্রে ব্যবহৃত হয়) নির্ধারণ করুন। উপরন্তু, dist-এ 0 বরাদ্দ করুন।
-
অন্যথায়, বৃদ্ধি বৃদ্ধি করুন।
-
সবশেষে, ডিস্ট এবং ম্যাক্সডিস্ট (তৃতীয় ক্ষেত্রে ব্যবহৃত হয়) এর সর্বাধিক রিটার্ন করুন।
উদাহরণ
// C++ program to calculate the maximum
// distance between any city
// and its nearest station
#include<bits/stdc++.h>
using namespace std;
// Shows function to compute the maximum
// distance between any city and its nearest station
int findMaxDistance(int numOfCities1,int station1[],int N){
// Used to initialize boolean list
bool hasStation[numOfCities1 + 1] = {false};
// Used to assign True to cities containing station
for (int city1 = 0; city1 < N; city1++){
hasStation[station1[city1]] = true;
}
int dist1 = 0;
int maxDist1 = INT_MAX;
for(int i = 0; i < N; i++){
maxDist1 = min(station1[i],maxDist1);
}
for (int city1 = 0; city1 < numOfCities1; city1++){
if (hasStation[city1] == true){
maxDist1 = max((dist1 + 1) / 2, maxDist1);
dist1 = 0;
}
else
dist1 += 1;
}
return max(maxDist1, dist1);
}
//Driver code
int main(){
int numOfCities1 = 6;
int station1[] = {2,4};
int N = sizeof(station1)/sizeof(station1[0]);
cout << "Max Distance:" << findMaxDistance(numOfCities1,
station1, N);
} আউটপুট
Max Distance:2
