अवधारणा
दिए गए शहरों की संख्या के संबंध में एन की संख्या 0 से एन -1 तक और जिन शहरों में स्टेशन स्थित हैं, हमारा काम किसी भी शहर और उसके निकटतम स्टेशन के बीच अधिकतम दूरी निर्धारित करना है। यह ध्यान दिया जाना चाहिए कि स्टेशनों वाले शहरों को किसी भी क्रम में दिया जा सकता है।
इनपुट
numOfCities = 6, stations = [2, 4]
आउटपुट
2
इनपुट
numOfCities = 6, stations = [4]
आउटपुट
4
-
निम्नलिखित आंकड़ा पहले उदाहरण को दर्शाता है जिसमें 6 शहरों और हरे रंग से हाइलाइट किए गए स्टेशनों वाले शहर शामिल हैं। तो, इस मामले में, अपने निकटतम स्टेशनों से सबसे दूर के शहर 2 की दूरी पर 0 हैं। इसलिए अधिकतम दूरी 1 है।
-
दूसरे उदाहरण में, अपने निकटतम स्टेशन से सबसे दूर का शहर 0 है जो 4 की दूरी पर है। इसलिए अधिकतम दूरी 4 है।
विधि
यहाँ, इस समस्या के तीन संभावित मामले हैं -
-
पहला मामला इंगित करता है कि सबसे दूर का शहर दो स्टेशनों के बीच कब है।
-
दूसरा मामला इंगित करता है कि सबसे दूर का शहर पहले स्टेशन के बाईं ओर है।
-
अंतिम मामला इंगित करता है कि सबसे दूर का शहर अंतिम स्टेशन के दाईं ओर कब है।
उपरोक्त समस्या को हल करने के लिए निम्नलिखित एल्गोरिथम लागू किया गया है -
-
हम गलत के साथ आकार एन (शहरों की संख्या) की एक बूलियन सरणी प्रारंभ करते हैं। उसके बाद स्टेशनों वाले शहरों के मूल्यों को सही के रूप में चिह्नित करें
-
इसके बाद हम 0 के साथ एक वेरिएबल डिस्ट को इनिशियलाइज़ करते हैं। हमें वैल्यू के साथ एक और वेरिएबलमैक्सडिस्ट को इनिशियलाइज़ करना होगा जो स्टेशन के साथ पहले शहर के समान है (दूसरे केस के लिए इस्तेमाल किया गया)।
-
सभी शहरों में एक-एक करके लूपिंग शुरू करें।
-
यह देखा गया है कि यदि वर्तमान शहर में एक स्टेशन है, और फिर अधिकतम (dist+1)//2 और maxDist को maxDist (पहले मामले के लिए प्रयुक्त) असाइन करें। इसके अलावा, जिले को 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