मान लीजिए हमारे पास N संख्या में शहर हैं, और वे 0 से N-1 तक क्रमांकित हैं और हमारे पास वे शहर भी हैं जिनमें स्टेशन स्थित हैं, हमें किसी भी शहर और उसके निकटतम स्टेशन के बीच अधिकतम दूरी ढूंढनी है। हमें इस बात का ध्यान रखना है कि स्टेशनों वाले शहर किसी भी क्रम में दिए जा सकते हैं।
तो, यदि इनपुट N = 6 और stations = [2,4] की तरह है, तो आउटपुट 2 होगा।
इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -
station_present := N आकार की एक सूची, और False से भरें
station में प्रत्येक शहर के लिए, करें
station_present[city] := True
dist := 0, maximum_dist := station का न्यूनतम
city के लिए 0 से N की सीमा में, करें
यदि station_present[city] True है, तो
maximum_dist := (dist + 1) / 2, maximum_dist का अधिकतम
dist := 0
अन्यथा,
dist := dist + 1
maximum_dist, dist का अधिकतम वापस करें
उदाहरण (Python)
बेहतर समझ पाने के लिए निम्नलिखित कार्यान्वयन देखें -
def get_max_dist(N, station): station_present = [False] * N for city in station: station_present[city] = True dist, maximum_dist = 0, min(station) for city in range(N): if station_present[city] == True: maximum_dist = max((dist + 1) // 2, maximum_dist) dist = 0 else: dist += 1 return max(maximum_dist, dist) N = 6 station = [2, 4] print(get_max_dist(N, station))
इनपुट
6, [2,4]
आउटपुट
2
