Pythonで任意の都市と駅の間の最大距離を見つける

N個の都市があり、それらに0からN-1までの番号が付けられており、駅が配置されている都市もあるとすると、任意の都市間の最大距離を見つける必要があります。市とその最寄りの駅。駅のある都市は任意の順序で指定できることに注意する必要があります。

したがって、入力がN =6、ステーション=[2,4]の場合、出力は2

これを解決するには、次の手順に従います-

• station_present：=サイズNのリスト、Falseで埋める

• 駅の各都市について、実行します

  • station_present [city]：=True

• dist：=0、maximum_dist：=ステーションの最小値

• 0からNの範囲の都市の場合、実行

  • station_present [city]がTrueの場合、

    • maximum_dist：=maximum of（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