Pythonで食べたリンゴの最大数を見つけるプログラム

同じ長さnの日とリンゴという2つの配列があるとします。 n日間連続して毎日リンゴを育てる特別な種類のリンゴの木があります。 i日目はリンゴ[i]の数のリンゴが育ち、それは数日[i]日後に腐敗するので、i日+日[i]のリンゴは腐って食べられなくなると言えます。ある日。 apples [i] =0、days [i] =0の場合、i日目に、リンゴの木はリンゴを成長させていないことを示します。私たちは1日にせいぜい1つのリンゴを取ることができます。 （最初のn日後も食べ続けることができます）。ここでは、食べられるリンゴの最大数を見つける必要があります。

したがって、入力がapples =[1,2,3,5,2] days =[3,2,1,4,2]の場合、-

• 1日目は初日に育ったリンゴを食べます。

• 2日目は2日目に育ったリンゴを食べます。

• 3日目は2日目に育ったリンゴを食べます。しかし、この日の後、3日目に成長したリンゴは腐ります。

• 4日目から7日目は、4日目に育ったリンゴを食べます。

これを解決するには、次の手順に従います-

• minheap：=新しい空のヒープ
• 日：=0、解像度：=0
• リンゴのサイズが0からリンゴのサイズまでの範囲のiの場合-1、実行
  • 日：=i
  • minheapが空ではなく、minheapの上部の値が腐敗している間-日、実行
    • minheapから最上位の要素を削除します
  • nbrApple：=apples [i]
  • 有効期限：=i+日[i]-1
  • nbrApple> 0の場合、
    • minheapに（expiration、nbrApple）ペアを挿入します
  • minheapが空でない場合は、
    • （date、apple）：=minheapの最上位要素であり、ヒープから削除します
    • res：=res + 1
    • アップル>1の場合、
      • minheapに（date、apple-1）ペアを挿入します
• minheapが空でない間は、
  • 日：=日+ 1
  • minheapが空ではなく、minheapの上部の値が腐敗している間<日、実行
    • minheapから最上位の要素を削除します
  • minheapが空の場合、
    • ループから抜け出す
  • （date、apple）：=minheapの先頭で、ヒープから削除します
  • res：=res + 1
  • アップル>1の場合、
    • minheapに（date、apple-1）ペアを挿入します
• return 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]

出力

7