Python中查詢任意城市和車站之間的最大距離

假設我們有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 in range 0 到 N，執行：

  • 如果station_present[city]為True，則

    • maximum_dist := max((dist + 1) / 2, maximum_dist)

    • dist := 0

  • 否則，

    • dist := dist + 1

• 返回max(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

Arnab Chakraborty

更新於：2020年8月25日

202 次瀏覽

開啟你的職業生涯

完成課程獲得認證

開始學習