在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，如图所示。

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

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

如果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))