পাইথনে সর্বাধিক সংখ্যক আপেল খাওয়ার জন্য প্রোগ্রাম

ধরুন আমাদের কাছে দিন নামক দুটি অ্যারে আছে এবং একই দৈর্ঘ্যের আপেল n। একটি বিশেষ ধরনের আপেল গাছ আছে যেটি প্রতিদিন n টানা দিন আপেল জন্মায়। প্রথম দিনে, এটি আপেলের সংখ্যা বৃদ্ধি করে এবং এটি কয়েক দিন পরে পচে যায়, তাই আমরা এটি বলতে পারি যে দিন i + দিন [i] আপেলগুলি পচে যাবে এবং খাওয়া যাবে না। কিছু দিনে। যদি আপেল[i] =0, এবং দিন[i] =0 হয়, তাহলে এটি ইঙ্গিত করে যে i দিনে, আপেল গাছে কোনো আপেল বাড়ছে না। আমরা দিনে সর্বাধিক একটি আপেল খেতে পারি। (আমরা প্রথম n দিনের পরে খাওয়া চালিয়ে যেতে পারি)। এখানে আমরা সর্বোচ্চ কতগুলি আপেল খেতে পারি তা খুঁজে বের করতে হবে।

সুতরাং, যদি ইনপুট আপেলের মত হয় =[1,2,3,5,2] দিন =[3,2,1,4,2], তাহলে আউটপুট হবে 7 কারণ −

প্রথম দিনে, আমরা একটি আপেল খাই যা প্রথম দিনে বেড়েছিল।
২য় দিনে, আমরা একটি আপেল খাই যা দ্বিতীয় দিনে বেড়ে ওঠে।
তৃতীয় দিনে, আমরা একটি আপেল খাই যা দ্বিতীয় দিনে বেড়ে ওঠে। কিন্তু এই দিনের পর, তৃতীয় দিনে বেড়ে ওঠা আপেলগুলো পচে যাবে।
4 থেকে 7 দিনগুলিতে, আমরা চতুর্থ দিনে বেড়ে ওঠা আপেল খাই৷

এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -

মিনহিপ :=একটি নতুন খালি গাদা
দিন :=0, রেস :=0
আমার জন্য 0 থেকে আপেলের আকার - 1, করুন
- দিন :=i
- যখন মিনহিপ খালি না থাকে এবং মিনহিপের টপ এর পচা মান − দিন, কর
  - মিনহিপ থেকে শীর্ষ উপাদান সরান
- nbrApple :=আপেল[i]
- মেয়াদ শেষ :=i + দিন[i]-1
- যদি nbrApple> 0 হয়, তাহলে
  - মিনহিপে যোগ করুন (মেয়াদ শেষ হওয়া, nbrApple) জোড়া
- যদি minheap খালি না হয়, তাহলে
  - (তারিখ, আপেল) :=মাইনহেপের শীর্ষ উপাদান এবং এটিকে স্তূপ থেকে সরিয়ে দিন
  - res :=res + 1
  - যদি আপেল> 1 হয়, তাহলে
    - মিনিহেপে (তারিখ, আপেল-১) জোড়া ঢোকান
যদিও মিনহেপ খালি না থাকে, কর
- দিন :=দিন + ১
- যখন মিনহিপ খালি না থাকে এবং মিনহিপের টপ এর পচা মান <দিন, কর
  - মিনহিপ থেকে শীর্ষ উপাদান সরান
- যদি minheap খালি হয়, তাহলে
  - লুপ থেকে বেরিয়ে আসুন
- (তারিখ, আপেল) :=মাইনহেপের শীর্ষ এবং এটিকে স্তূপ থেকে সরান
- res :=res + 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]