在Python中查找可以吃的苹果的最大数量的程序

假设我们有两个名为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天，我们吃了第1天生长的苹果。
在第2天，我们吃了第2天生长的苹果。
在第3天，我们吃了在第2天生长的苹果，并且在此之后，第3天生长的苹果将腐烂。
在4到7天，我们吃的是第4天生长的苹果。

为了解决这个问题，我们将按照以下步骤进行 –

minheap:=一个新的空堆
day:=0，res:=0
对于范围从0到apples长度-1的i，执行以下操作 –
- day:=i
- 当minheap不为空并且minheap顶部的rot值为day时，先弹出堆顶元素，直到无法继续弹出为止
  - 从minheap中删除顶部元素
- nbrApple:= apples[i]
- expiration:= i + days[i]-1
- 如果nbrApple>0，则
  - 将（expiration，nbrApple）对插入到minheap中
- 如果minheap不为空，则
  - (date，apple):=minheap的顶部元素，并从minheap中删除它
  - res:=res+1
  - 如果apple > 1，然后 –
  - 将（date，apple-1）对插入到minheap
当minheap不为空时，执行以下操作 –
- day:= day + 1
- 当minheap不为空并且minheap顶部的rot值小于day时，将minheap顶部的元素弹出，直到无法继续弹出为止
  - 从minheap中删除顶部元素
- 如果minheap为空，则 –
  - 退出循环
- date，apple := minheap的顶部元素，并从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))