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 次浏览

开启你的职业生涯

完成课程获得认证

开始学习