สมมติว่ามีบ้านจำนวน n หลังที่มีความสูงต่างกัน และศิลปินปาร์กัวร์ต้องการย้ายจากบ้านหนึ่งไปอีกหลังหนึ่งโดยใช้อิฐและบันไดช่วย ความสูงของบ้านให้เราเป็นแถว อิฐแต่ละก้อนมีความสูงหนึ่งหน่วยและเราจะได้รับจำนวนหนึ่ง เราสามารถใช้บันไดและอิฐได้เพียงครั้งเดียวเท่านั้น เราต้องหาตึกที่ไกลที่สุดที่ศิลปิน parkour ไปได้
ดังนั้น หากอินพุตเท่ากับความสูง =[5, 8, 7, 6, 2, 3, 1, 4], อิฐ =3, บันได =2 ผลลัพธ์จะเป็น 7
ศิลปินเริ่มจากตึก 0
เขาไปถึงอาคาร 1 ด้วยอิฐ 3 ก้อน
เขากระโดดไปที่อาคาร 2, 3, 4 เนื่องจากอาคารที่ตามมานั้นสั้นกว่าอาคารรุ่นก่อน
เขาใช้บันไดเพื่อไปจากอาคาร 4 ไปอาคาร 5
เขากระโดดจากอาคาร 5 ไปยังอาคาร 6 เนื่องจากอาคาร 6 นั้นสั้นกว่า
เขาใช้บันไดสุดท้ายเพื่อไปถึงตึก 7
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -
-
temp :=ฮีปใหม่
-
สำหรับผมอยู่ในช่วง 1 ถึงขนาดความสูง ทำ
-
dist :=heights[i] - heights[i - 1]
-
ถ้า dist> 0 แล้ว
-
อิฐ :=อิฐ - dist
-
ดันค่า -dist ไปที่ฮีปชั่วคราว
-
ถ้าอิฐ <0 แล้ว
-
บันได :=บันได - 1
-
อิฐ :=อิฐ - องค์ประกอบที่เล็กที่สุดถูกลบออกจากอุณหภูมิฮีป
-
ถ้าอิฐ <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
ผลลัพธ์
7
