用 Python 编写程序来查找建筑物的最大高度

pythonserver side programmingprogramming更新于 2025/12/14 7:08:17

假设我们有一个值 n 和另一个称为限制的对列表。我们想在一个城市建造 n 座新建筑。但限制很少。我们可以排成一行，并将建筑物标记为从 1 到 n。限制有两个参数，因此限制[i] = (id_i, max_height_i) 表示 id_i 的高度必须小于或等于 max_height_i。城市对新建筑高度的限制如下 −

每栋建筑的高度必须为 0 或正值。
第一栋建筑的高度必须为 0。
任何两栋相邻建筑的高度差不能超过 1。

我们必须找到最高建筑的最大可能高度。

因此，如果输入为 n = 5，限制 = [[2,1],[4,3]]，则输出将为 4，因为我们必须找到最大可能高度，因此它可以是 4，如图所示。

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

如果 requirements 为空，则
- 返回 n-1
resi := 根据 id 对限制列表进行排序
k := 0
idx := 1
对于 resi 中的每个 re，执行
- re[1] := re[1] 和 (k+re[0]-idx) 中的最小值
- k := re[1]
- idx := re[0]
k := resi 中最后一个元素的最大高度
idx := resi 中最后一个元素的 id
反转列表 resi
对于 resi 中从第一项开始的每个 re，执行
- re[1] := re[1] 和 (k-re[0]+idx) 的最小值
- k := re[1]
- idx := re[0]
反转列表 resi
f := 0
idx := 1
res := 0
对于 resi 中的每个 re，执行
- ff := (f+re[0]-idx) 和 re[1] 的最小值
- res := res 的最大值和 (re[0] - idx + f + ff)/2 的商
- idx := re[0]
- f := ff
返回 (f+n-idx) 和 res 的最大值

示例

让我们看看下面的实现以便更好地理解

def solve(n, restrictions):
   if not restrictions:
      return n-1
   resi = sorted(restrictions, key = lambda x:x[0])

   k = 0
   idx = 1
   for re in resi:
      re[1] = min(re[1], k+re[0]-idx)
      k = re[1]
      idx = re[0]
   k = resi[-1][1]
   idx = resi[-1][0]
   resi.reverse()
   for re in resi[1:]:
      re[1] = min(re[1], k-re[0]+idx)
      k = re[1]
      idx = re[0]
   resi.reverse()

   f = 0
   idx = 1
   res = 0
   for re in resi:
      ff = min(f+re[0]-idx, re[1])
      res = max(res, (re[0] - idx + f + ff) // 2)
      idx = re[0]
      f = ff
   return max(f+n-idx,res)

n = 5
restrictions = [[2,1],[4,3]]
print(solve(n, restrictions))