โปรแกรมหาตึกที่ไกลที่สุดที่นักพาร์คอร์สามารถถึงได้ใน Python

ปัญหา

มีตึกสูงต่างกัน heights นักพาร์คอร์เริ่มตึก 0 มีอิฐ (ความสูง 1 หน่วย) และไม้ค้ำ ต้องขึ้นตึกที่สูงกว่า ใช้อิฐหรือไม้ค้ำ (ใช้ครั้งละ 1) หาตึกสุดท้ายที่ถึงได้

ตัวอย่าง

heights=[5,8,7,6,2,3,1,4], bricks=3, ladders=2 → ผลลัพธ์ 7 (ใช้อิฐขึ้น 5→8, ไม้ค้ำ 2→3, 1→4)

ขั้นตอนการแก้ปัญหา

1. temp := min-heap
2. วน i 1 ถึง n-1:
   • dist := heights[i] - heights[i-1]
   • ถ้า dist > 0:
     • bricks -= dist
     • heappush(temp, -dist)
     • ถ้า bricks < 0:
       • ladders -= 1
       • bricks -= heappop(temp) (คืนอิฐจากช่องว่างมากที่สุด)
       • ถ้า bricks < 0 or ladders < 0: คืน i-1
3. คืน len(heights)-1

การนำไปใช้งาน (Python)

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

เอาต์พุต

7