使用 Python 查找任意城市与车站之间的最大距离

pythonserver side programmingprogramming更新于 2025/10/10 15:40:17

假设我们有 N 个城市,它们的编号从 0 到 N-1,并且我们还有车站所在的城市,我们必须查找任意城市与其最近车站之间的最大距离。我们必须记住,有车站的城市可以按任何顺序给出。

因此,如果输入为 N = 6 且 stations = [2,4],则输出将为 2

为了解决这个问题,我们将遵循以下步骤 −

  • station_present := 大小为 N 的列表,并填充 False

  • 对于 station 中的每个城市,执行

    • station_present[city] := True

  • dist := 0, maximum_dist := minimum of station

  • 对于范围为 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

相关文章


有用资源