Giả sử, có n số ngôi nhà có chiều cao khác nhau và một nghệ sĩ parkour muốn đi từ ngôi nhà này sang ngôi nhà khác với sự trợ giúp của một số viên gạch và thang. Chiều cao của các ngôi nhà được cung cấp cho chúng ta dưới dạng một mảng. Mỗi viên gạch cao một đơn vị chiều dài và chúng tôi được cung cấp một số ít trong số đó. Chúng ta chỉ có thể sử dụng thang và gạch một lần. Chúng tôi phải tìm ra tòa nhà xa nhất mà nghệ sĩ parkour có thể đến.
Vì vậy, nếu đầu vào giống như heights =[5, 8, 7, 6, 2, 3, 1, 4], brick =3, ladders =2, thì đầu ra sẽ là 7.
Người nghệ sĩ bắt đầu từ việc xây dựng 0.
Anh ấy đạt được tòa nhà 1 với sự trợ giúp của 3 viên gạch.
Anh ta chuyển sang tòa nhà 2, 3, 4 vì các tòa nhà kế tiếp ngắn hơn các tòa nhà tiền nhiệm.
Anh ấy sử dụng một cái thang để đi từ tòa nhà 4 đến tòa nhà 5.
Anh ta nhảy từ tòa nhà 5 sang tòa nhà 6 vì tòa nhà 6 ngắn hơn.
Anh ta sử dụng bậc thang cuối cùng để đến tòa nhà 7.
Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -
-
temp:=a new heap
-
đối với tôi trong phạm vi từ 1 đến kích thước chiều cao, hãy thực hiện
-
dist:=heights [i] - heights [i - 1]
-
nếu dist> 0, thì
-
gạch:=gạch - dist
-
đẩy giá trị -dist lên heap temp
-
nếu gạch <0, thì
-
thang:=thang - 1
-
gạch:=gạch - phần tử nhỏ nhất bị xóa khỏi nhiệt độ đống
-
nếu gạch <0 hoặc thang <0, thì
-
trả lại i - 1
-
-
-
-
-
trả về kích thước chiều cao - 1
Ví dụ
Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -
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