পাইথনে যেকোনো সিটি এবং স্টেশনের মধ্যে সর্বোচ্চ দূরত্ব বের করা

ধরা যাক N সংখ্যক সিটি আছে 0 থেকে N-1 নম্বর দিয়ে, এবং কিছু সিটিতে স্টেশন আছে। আমাদের যেকোনো সিটি থেকে তার নিকটতম স্টেশনের দূরত্বের সর্বোচ্চ মান বের করতে হবে। স্টেশনগুলো যেকোনো অর্ডারে দেওয়া থাকতে পারে।

যেমন, N=6, stations=[2,4] হলে আউটপুট 2।

সমাধানের ধাপসমূহ

• station_present[N] বুলিয়ান অ্যারে (False দিয়ে ভরা)
• প্রতিটি স্টেশন সিটির জন্য station_present[city] = True
• dist=0, maximum_dist=min(station)
• for city in 0..N-1:
  • যদি station_present[city]: maximum_dist = max((dist+1)//2, maximum_dist); dist=0
  • অন্যথায়: dist += 1
• return max(maximum_dist, dist)

উদাহরণ

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]:
            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