Simulation volume leetcode [general] 1705 The maximum number of apples to eat

1705. The maximum number of apples to eat

There's a special apple tree , One after another n God , Several apples can grow every day . In the i God , Trees grow apples[i] An apple , These apples will be in days[i] Days later （ in other words , The first i + days[i] days ） Rot , Become inedible . Maybe for a few days , New apples don't grow on trees , Use at this time apples[i] == 0 And days[i] == 0 Express .

You're going to... Every day most Eat an apple to keep a balanced diet . Be careful , You can be here n Keep eating apples after three days .

Here are two lengths for you n Array of integers for days and apples , Return the maximum number of apples you can eat .

Example 1：

Input ：apples = [1,2,3,5,2], days = [3,2,1,4,2]
Output ：7
explain ： You can eat 7 An apple ：

• The first day , You eat the apples that grow on the first day .
• the second day , You eat an apple that grows the next day .
• On the third day , You eat an apple that grows the next day . After this day , On the third day, the apple has rotted .
• From day four to day seven , You eat apples that grow on the fourth day .
  Example 2：

Input ：apples = [3,0,0,0,0,2], days = [3,0,0,0,0,2]
Output ：5
explain ： You can eat 5 An apple ：

• From day one to day three , You eat apples that grow on the first day .
• No apples for the fourth and fifth days .
• The sixth and seventh days , You eat apples that grow on the sixth day .

Tips ：

apples.length == n
days.length == n
1 <= n <= 2 * 104
0 <= apples[i], days[i] <= 2 * 104
Only in apples[i] = 0 when ,days[i] = 0 It was established.

source ： Power button （LeetCode）
link ：https://leetcode-cn.com/problems/maximum-number-of-eaten-apples
Copyright belongs to the network . For commercial reprint, please contact the official authority , Non-commercial reprint please indicate the source .

Code ：

import heapq

from leetcode_python.utils import *


class Solution:
    def __init__(self):
        pass

    def eatenApples(self, apples: List[int], days: List[int]) -> int:
        remains = []
        index = res = 0
        length = len(days)
        while remains or index<length:
            while remains and remains[0][0]<=index:heapq.heappop(remains)
            if index<length and apples[index]:heapq.heappush(remains,[days[index]+index,apples[index]])
            if remains:
                if remains[0][1]>1:remains[0][1]-=1
                else:heapq.heappop(remains)
                res+=1
            index+=1
        return res


def test(data_test):
    s = Solution()
    data = data_test  # normal
    # data = [list2node(data_test[0])] # list turn node
    return s.eatenApples(*data)


def test_obj(data_test):
    result = [None]
    obj = Solution(*data_test[1][0])
    for fun, data in zip(data_test[0][1::], data_test[1][1::]):
        if data:
            res = obj.__getattribute__(fun)(*data)
        else:
            res = obj.__getattribute__(fun)()
        result.append(res)
    return result


if __name__ == '__main__':
    datas = [
        [[1,2,3,5,2],[3,2,1,4,2]],
    ]
    for data_test in datas:
        t0 = time.time()
        print('-' * 50)
        print('input:', data_test)
        print('output:', test(data_test))
        print(f'use time:{
      time.time() - t0}s')

remarks ：
GitHub：https://github.com/monijuan/leetcode_python

CSDN Summary ： Simulation volume Leetcode Summary of questions _ Paper blog -CSDN Blog

You can add QQ Group communication ：1092754609

leetcode_python.utils See the description on the summary page for details
First brush questions , Then generated by script blog, If there is any mistake, please leave a message , I see it will be revised ！ thank you ！