값 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가 될 수 있습니다. 도표.
이 문제를 해결하기 위해 다음 단계를 따릅니다. −
-
제한이 비어 있으면
-
n-1 반환
-
-
resi :=id에 따라 목록 제한 정렬
-
k :=0
-
아이디:=1
-
resi의 각 re에 대해 수행
-
re[1] :=re[1] 및 (k+re[0]-idx)의 최소값
-
k :=re[1]
-
idx :=re[0]
-
-
k :=resi의 마지막 요소의 최대 높이
-
idx :=resi의 마지막 요소 ID
-
목록 뒤집기
-
첫 번째 항목부터 각 항목에 대해 다음을 수행하십시오.
-
re[1] :=re[1] 및 (k-re[0]+idx)의 최소값
-
k :=re[1]
-
idx :=re[0]
-
-
목록 뒤집기
-
f :=0
-
아이디:=1
-
해상도 :=0
-
resi의 각 re에 대해 수행
-
ff :=(f+re[0]-idx) 및 re[1]의 최소값
-
res :=res의 최대값과 (re[0] - idx + f + ff)/2의 몫
-
idx :=re[0]
-
f :=f
-
-
(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