পাইথনে সর্বোচ্চ আপেল খাওয়ার প্রোগ্রাম

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

যেমন, ইনপুট apples = [1,2,3,5,2], days = [3,2,1,4,2] হলে, আউটপুট হবে ৭ কারণ:

দিন ১: প্রথম দিনের আপেল খাই।
দিন ২: দ্বিতীয় দিনের আপেল খাই।
দিন ৩: দ্বিতীয় দিনের আপেল খাই। এই দিনের পর তৃতীয় দিনের আপেলগুলো সড়ে যাবে।
দিন ৪ থেকে ৭: চতুর্থ দিনের আপেলগুলো খাই।

সমাধান পদ্ধতি

এই সমস্যাটি সমাধান করতে নিচের ধাপগুলো অনুসরণ করুন:

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]