Chương trình tìm tòa nhà xa nhất người nhảy parkour có thể đến trong Python

Mảng heights độ cao các tòa nhà. Người nhảy từ 0, có bricks gạch (mỗi gạch 1 đơn vị cao) và ladders thang (bất kỳ độ cao). Chỉ dùng 1 lần mỗi vật. Tìm chỉ số tòa nhà xa nhất có thể đến.

Ví dụ: heights=[5,8,7,6,2,3,1,4], bricks=3, ladders=2 → 7. Dùng gạch lên tầng 1 (cao 3), nhảy tự do đến tầng 4, thang lên tầng 5, nhảy đến 6, thang lên 7.

Giải thuật (Heap ưu tiên thang cho độ cao lớn)

1. Heap temp lưu độ cao chênh lệch (dương) đã dùng gạch (lưu âm để max-heap).
2. Duyệt i từ 1..n-1:
   • dist = heights[i] - heights[i-1].
   • Nếu dist > 0: dùng gạch (bricks -= dist), push -dist vào heap.
   • Nếu bricks < 0: đổi gạch lớn nhất thành thang (bricks -= heappop(temp), ladders--).
   • Nếu bricks < 0 hoặc ladders < 0: trả về i-1.
3. Trả về n-1.

Ví dụ minh họa

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

Đầu vào

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

Đầu ra

7