파쿠르 예술가가 도달할 수 있는 가장 먼 건물을 파이썬으로 찾는 프로그램

<시간/>

높이가 다른 n개의 집이 있고 파쿠르 예술가가 벽돌과 사다리를 사용하여 한 집에서 다른 집으로 이동하려고 한다고 가정합니다. 집의 높이는 배열로 제공됩니다. 각 벽돌은 높이가 단위 길이이며 소수가 제공됩니다. 사다리와 벽돌은 한 번만 사용할 수 있습니다. 파쿠르 예술가가 갈 수 있는 가장 먼 건물을 찾아야 합니다.

따라서 입력이 height =[5, 8, 7, 6, 2, 3, 1, 4], 벽돌 =3, 사다리 =2와 같으면 출력은 7이 됩니다.

아티스트는 건물 0부터 시작합니다.

그는 3개의 벽돌을 사용하여 건물 1에 도달합니다.

후속 건물이 이전 건물보다 짧기 때문에 그는 건물 2, 3, 4로 점프합니다.

그는 사다리를 사용하여 건물 4에서 건물 5로 이동합니다.

그는 건물 6이 더 짧기 때문에 건물 5에서 건물 6으로 점프합니다.

그는 마지막 사다리를 사용하여 건물 7에 도달합니다.

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

temp :=새 힙
범위 1에서 높이 크기까지의 i에 대해
- dist :=높이[i] - 높이[i - 1]
- dist> 0이면
  - 벽돌 :=벽돌 - dist
  - push value -dist to heap temp
  - 벽돌 <0이면
    - 사다리 :=사다리 - 1
    - bricks :=bricks - 힙 온도에서 제거된 가장 작은 요소
    - 벽돌 <0 또는 사다리 <0이면
      - 반환 i - 1
높이의 크기 반환 - 1

예

이해를 돕기 위해 다음 구현을 살펴보겠습니다. −

from heapq import heappush, heappop
def solve(heights, bricks, ladders):
   temp = []
   for i in range(1, len(heights)):
      dist = heights[i] - heights[i - 1]
      if dist > 0:
         bricks -= dist
         heappush(temp, -dist)
         if bricks < 0:
            ladders -= 1
            bricks -= heappop(temp)
            if bricks < 0 or ladders < 0:
               return i - 1
   return len(heights) - 1

print(solve([5, 8, 7, 6, 2, 3, 1, 4], 3, 2))

입력

[5, 8, 7, 6, 2, 3, 1, 4], 3, 2