資料結構
網路
關係資料庫管理系統(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 次瀏覽
