मान लीजिए, अलग-अलग ऊंचाई के n घर हैं और एक पार्कूर कलाकार कुछ ईंटों और सीढ़ियों की मदद से एक घर से दूसरे घर जाना चाहता है। घरों की ऊंचाई हमें एक ऐरे के रूप में दी गई है। प्रत्येक ईंट एक यूनिट लंबी होती है और हमें उनमें से कुछ दी गई हैं। हम सीढ़ियों और ईंटों का उपयोग केवल एक बार कर सकते हैं। हमें पता लगाना है कि पार्कूर कलाकार सबसे दूर किस इमारत तक जा सकता है।
उदाहरण के लिए, यदि इनपुट है heights = [5, 8, 7, 6, 2, 3, 1, 4], bricks = 3, ladders = 2, तो आउटपुट 7 होगा।
कलाकार बिल्डिंग 0 से शुरू करता है।
वह 3 ईंटों की मदद से बिल्डिंग 1 तक पहुंचता है।
वह बिल्डिंग 2, 3, 4 पर कूदता है क्योंकि उत्तराधिकारी इमारतें पूर्ववर्ती से छोटी हैं।
वह बिल्डिंग 4 से बिल्डिंग 5 तक जाने के लिए एक सीढ़ी का उपयोग करता है।
वह बिल्डिंग 5 से बिल्डिंग 6 पर कूदता है क्योंकि बिल्डिंग 6 छोटी है।
वह अंतिम सीढ़ी का उपयोग करके बिल्डिंग 7 तक पहुंचता है।
समाधान के चरण
temp :=एक नया हीपiको 1 सेlen(heights)तक:dist := heights[i] - heights[i-1]- यदि
dist > 0:bricks := bricks - distheappush(temp, -dist)- यदि
bricks < 0:ladders := ladders - 1bricks := bricks - heappop(temp)- यदि
bricks < 0 or ladders < 0:i - 1वापस करें
len(heights) - 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