अवधारणा
0 से N-1 तक संख्या वाले शहरों की दी गई संख्या N और जिन शहरों में स्टेशन स्थित हैं, के संबंध में, हमारा कार्य किसी भी शहर और उसके निकटतम स्टेशन के बीच अधिकतम दूरी निर्धारित करना है। यह ध्यान दिया जाना चाहिए कि स्टेशनों वाले शहर किसी भी क्रम में दिए जा सकते हैं।
इनपुट
numOfCities = 6, stations = [2, 4]
आउटपुट
2
इनपुट
numOfCities = 6, stations = [4]
आउटपुट
4
निम्नलिखित आकृति पहले उदाहरण को दर्शाती है जिसमें 6 शहर हैं और स्टेशनों वाले शहर हरे रंग से हाइलाइट किए गए हैं। तो, इस मामले में, उसके निकटतम स्टेशनों से सबसे दूर का शहर 0 है जो 2 की दूरी पर है। इसलिए अधिकतम दूरी 1 है।

दूसरे उदाहरण में, उसके निकटतम स्टेशन से सबसे दूर का शहर 0 है जो 4 की दूरी पर है। इसलिए अधिकतम दूरी 4 है।

विधि
यहां, इस समस्या में तीन संभावित मामले हैं −
पहला मामला इंगित करता है जब सबसे दूर का शहर दो स्टेशनों के बीच होता है।
दूसरा मामला इंगित करता है जब सबसे दूर का शहर पहले स्टेशन के बाईं ओर होता है।
अंतिम मामला इंगित करता है जब सबसे दूर का शहर अंतिम स्टेशन के दाईं ओर होता है।
उपरोक्त समस्या को हल करने के लिए निम्नलिखित एल्गोरिदम लागू किया जाता है −
हम आकार N (शहरों की संख्या) का एक बूलियन सरणी False के साथ इनिशियलाइज़ करते हैं। उसके बाद स्टेशनों वाले शहरों के मानों को True के रूप में चिह्नित करें
इसके बाद हम एक वेरिएबल dist को 0 से इनिशियलाइज़ करते हैं। हमें एक और वेरिएबल maxDist को इनिशियलाइज़ करना होगा जिसका मान पहले स्टेशन वाले शहर के समान हो (दूसरे मामले के लिए उपयोग किया जाता है)।
एक-एक करके सभी शहरों के माध्यम से लूप शुरू करें।
यह देखा गया है कि यदि वर्तमान शहर में स्टेशन है, और फिर (dist+1)//2 और maxDist के अधिकतम को maxDist को असाइन करें (पहले मामले के लिए उपयोग किया जाता है)। इसके अलावा, dist को 0 असाइन करें।
अन्यथा, dist को बढ़ाएं।
अंत में, dist और maxDist के अधिकतम को लौटाएं (तीसरे मामले के लिए उपयोग किया जाता है)।
उदाहरण
// C++ program to calculate the maximum // distance between any city // and its nearest station #include<bits/stdc++.h> using namespace std; // किसी भी शहर और उसके निकटतम स्टेशन के बीच अधिकतम // दूरी की गणना करने वाला फ़ंक्शन int findMaxDistance(int numOfCities1,int station1[],int N){ // बूलियन सूची को इनिशियलाइज़ करने के लिए उपयोग किया जाता है bool hasStation[numOfCities1 + 1] = {false}; // स्टेशन वाले शहरों को True असाइन करने के लिए उपयोग किया जाता है 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); } //ड्राइवर कोड 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