मान लीजिए हमारे पास nums नामक एक पूर्णांक सरणी है, हमारे पास दो अन्य मान m और k भी हैं। अब, हमें m बुके बनाने हैं। एक बुके बनाने के लिए हमें बगीचे से k आसन्न फूल चाहिए। यहां बगीचे में n अलग-अलग फूल हैं, ith फूल bloomDay[i] में खिलेगा। प्रत्येक फूल का उपयोग केवल एक बुके में किया जा सकता है। हमें बगीचे से m बुके बनाने के लिए प्रतीक्षा करने के लिए न्यूनतम दिनों की संख्या ढूंढनी है। यदि हम m बुके नहीं बना सकते, तो -1 वापस करें।
उदाहरण के लिए, यदि इनपुट bloomDay = [5,5,5,5,10,5,5] m = 2 k = 3 है, तो आउटपुट 10 होगा क्योंकि हमें 2 (m = 2) बुके चाहिए और प्रत्येक में 3 फूल होने चाहिए।
दिन 5 के बाद: [x, x, x, x, _, x, x], हम पहले तीन खिले फूलों का एक बुके बना सकते हैं, लेकिन दूसरा बुके नहीं बना सकते
दिन 10 के बाद: [x, x, x, x, x, x, x], अब हम दो बुके अलग-अलग तरीकों से बना सकते हैं।
हल करने के चरण
n := bloomDay का आकार
यदि m * k > n, तो
-1 वापस करें
एक फ़ंक्शन possible() परिभाषित करें। यह x लेगा
count := 0, bouquets := 0
bloomDay में प्रत्येक d के लिए, करें
यदि d <= x, तो
count := count + 1
यदि count, k के समान है, तो
bouquets := bouquets + 1
count := 0
अन्यथा,
count := 0
यदि bouquets >= m तो true वापस करें, अन्यथा false
मुख्य विधि से निम्नलिखित करें -
left := 0, right := 1 + bloomDay का अधिकतम
जब तक left < right, करें
mid := (left + right) / 2
यदि possible(mid) true है, तो
right := mid
अन्यथा,
left := mid + 1
यदि possible(left) true है, तो
left वापस करें
अन्यथा left + 1 वापस करें
उदाहरण
def solve(bloomDay, m, k):
n = len(bloomDay)
if m * k > n:
return -1
def possible(x):
count = 0
bouquets = 0
for d in bloomDay:
if d <= x:
count += 1
if count == k:
bouquets += 1
count = 0
else:
count = 0
return bouquets >= m
left, right = 0, max(bloomDay) + 1
while left < right:
mid = (left + right) // 2
if possible(mid):
right = mid
else:
left = mid + 1
if possible(left):
return left
else:
return left + 1
bloomDay = [5,5,5,5,10,5,5]
m = 2
k = 3
print(solve(bloomDay, m, k))
इनपुट
[5,5,5,5,10,5,5], 2, 3
आउटपुट
10
