पायथन में खाए गए सेबों की अधिकतम संख्या खोजने का कार्यक्रम

मान लीजिए कि हमारे पास दो सरणियाँ हैं जिन्हें दिन कहा जाता है और एक ही लंबाई के सेब n हैं। एक विशेष प्रकार का सेब का पेड़ है जो लगातार n दिनों तक हर दिन सेब उगाता है। सातवें दिन, यह सेबों की संख्या [i] सेब उगाता है और जो दिनों [i] दिनों के बाद सड़ जाएगा, इसलिए हम इसे ऐसे कह सकते हैं कि जिस दिन मैं + दिन [i] सेब सड़ जाएगा और खाया नहीं जा सकता। कुछ दिनों में। यदि सेब [i] =0, और दिन [i] =0, तो यह इंगित करता है कि पहले दिन, सेब का पेड़ कोई सेब नहीं उगा रहा है। हम एक दिन में ज्यादा से ज्यादा एक सेब ले सकते हैं। (हम पहले n दिनों के बाद भी खाना जारी रख सकते हैं)। यहां हमें यह पता लगाना है कि हम कितने सेब खा सकते हैं।

इसलिए, यदि इनपुट सेब की तरह है =[1,2,3,5,2] दिन =[3,2,1,4,2], तो आउटपुट 7 होगा क्योंकि -

• पहले दिन हम एक सेब खाते हैं जो पहले दिन बढ़ा था।

• दूसरे दिन हम एक सेब खाते हैं जो दूसरे दिन बड़ा हुआ।

• तीसरे दिन हम एक सेब खाते हैं जो दूसरे दिन बड़ा हुआ। लेकिन इस दिन के बाद तीसरे दिन उगने वाले सेब सड़ जाएंगे।

• 4 से 7 के दिनों में हम चौथे दिन उगे सेब खाते हैं।

इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -

• मिनहीप :=एक नया खाली ढेर
• दिन :=0, रेस :=0
• i के लिए 0 से लेकर सेब के आकार -1 तक के लिए
  • दिन:=मैं
  • जबकि minheap खाली नहीं है और minheap के शीर्ष का मूल्य - दिन, do
    • मिनहेप से शीर्ष तत्व निकालें
  • nbrApple:=सेब[i]
  • समाप्ति :=i + दिन[i]-1
  • अगर nbrApple> 0, तो
    • मिनहेप में (एक्सपायरी, nbrApple) पेयर डालें
  • यदि मिनहीप खाली नहीं है, तो
    • (तारीख, सेब) :=minheap का शीर्ष तत्व और इसे हीप से हटा दें
    • रेस :=रेस + 1
    • अगर सेब> 1, तो
      • मिनहेप में (तारीख, सेब-1) जोड़ी डालें
• जबकि minheap खाली नहीं है, करें
  • दिन :=दिन + 1
  • जबकि minheap खाली नहीं है और minheap के शीर्ष का मूल्य <दिन, do
    • मिनहेप से शीर्ष तत्व निकालें
  • अगर मिनहीप खाली है, तो
    • लूप से बाहर आएं
  • (तारीख, सेब) :=minheap के ऊपर और इसे हीप से हटा दें
  • रेस :=रेस + 1
  • अगर सेब> 1, तो
    • मिनहेप में (तारीख, सेब-1) जोड़ी डालें
• रिटर्न रेस

उदाहरण

आइए बेहतर समझ पाने के लिए निम्नलिखित कार्यान्वयन देखें -

import heapq
def solve(apples, days):
   minheap = []
   heapq.heapify(minheap)
   day = 0
   res = 0
   for i in range(len(apples)):
      day = i

      while minheap and minheap[0][0] < day:
         heapq.heappop(minheap)

      nbrApple = apples[i]
      expiration = i + days[i]-1

      if nbrApple > 0:
         heapq.heappush(minheap, (expiration, nbrApple))

      if minheap:
         date, apple = heapq.heappop(minheap)
         res += 1
         if apple > 1:
            heapq.heappush(minheap, (date, apple-1))

   while minheap:
      day += 1
      while minheap and minheap[0][0] < day:
         heapq.heappop(minheap)
      if minheap == []:
         break
      date, apple = heapq.heappop(minheap)
      res += 1
      if apple > 1:
         heapq.heappush(minheap, (date, apple-1))

   return res

apples = [1,2,3,5,2]
days = [3,2,1,4,2]
print(solve(apples, days))

इनपुट

[1,2,3,5,2],[3,2,1,4,2]

आउटपुट

7