数据结构
网络
关系数据库管理系统(RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装设计
法学Python程序：查找最大建筑物高度
假设我们有一个值n和另一个称为限制的成对列表。我们想在一个城市中建造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
对于每个re in resi，执行：
re[1] := re[1]和(k+re[0]-idx)的最小值
k := re[1]
idx := re[0]
k := resi中最后一个元素的最大高度
idx := resi中最后一个元素的id
反转列表resi
对于从第一个项目开始的每个re in resi，执行：
re[1] := re[1]和(k-re[0]+idx)的最小值
k := re[1]
idx := re[0]
反转列表resi
f := 0
idx := 1
res := 0
对于每个re in resi，执行：
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))输入
5, [[2,1],[4,3]]
输出
4
695 次浏览
