在Python中查找最大建筑高度的程序

假设我们有一个值n和另一个名为restrictions的配对列表。我们想在城市中建造n座新建筑物。但有一些限制。我们可以沿着一条线建造建筑物，建筑物从1到n编号。这些限制有两个参数，因此restrictions[i] =（id_i，max_height_i）表示id_i的高度必须小于或等于max_height_i。新建筑物的城市高度限制如下：

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

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

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

要解决这个问题，我们将按照以下步骤进行 –

• 如果restrictions为空，则
• 返回n-1
• resi：=基于ID对列表restrictions进行排序
• 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：=（re[0] – idx + f + ff）// 2的商和res的最大值
• 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))

输入

5, [[2,1],[4,3]]

输出

4