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

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

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

दिन 1 पर, हम पहले दिन उगा एक सेब खाते हैं।
दिन 2 पर, हम दूसरे दिन उगा एक सेब खाते हैं।
दिन 3 पर, हम दूसरे दिन उगा एक सेब खाते हैं। लेकिन इस दिन के बाद, तीसरे दिन उगे सेब सड़ जाएंगे।
दिन 4 से 7 तक, हम चौथे दिन उगे सेब खाते हैं।

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

minheap := एक नया खाली हीप
day := 0, res := 0
i को 0 से apples के आकार - 1 तक के लिए, करें
- day := i
- जब तक minheap खाली नहीं है और minheap के शीर्ष का सड़ने का मान - day, करें
  - minheap से शीर्ष तत्व हटाएं
- nbrApple := apples[i]
- expiration := i + days[i]-1
- यदि nbrApple > 0, तो
  - (expiration, nbrApple) जोड़ी को minheap में डालें
- यदि minheap खाली नहीं है, तो
  - (date, apple) := minheap का शीर्ष तत्व और इसे हीप से हटाएं
  - res := res + 1
  - यदि apple > 1, तो
    - (date, apple-1) जोड़ी को minheap में डालें
जब तक minheap खाली नहीं है, करें
- day := day + 1
- जब तक minheap खाली नहीं है और minheap के शीर्ष का सड़ने का मान < day, करें
  - minheap से शीर्ष तत्व हटाएं
- यदि minheap खाली है, तो
  - लूप से बाहर आएं
- (date, apple) := minheap का शीर्ष और इसे हीप से हटाएं
- res := res + 1
- यदि apple > 1, तो
  - (date, apple-1) जोड़ी को minheap में डालें
res वापस करें

उदाहरण

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

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]