题目

有一棵特殊的苹果树，一连 n 天，每天都可以长出若干个苹果。在第 i 天，树上会长出 apples[i] 个苹果，这些苹果将会在 days[i] 天后（也就是说，第 i + days[i] 天时）腐烂，变得无法食用。也可能有那么几天，树上不会长出新的苹果，此时用 apples[i] == 0 且 days[i] == 0 表示。

你打算每天最多吃一个苹果来保证营养均衡。注意，你可以在这 n 天之后继续吃苹果。

给你两个长度为 n 的整数数组 days 和 apples ，返回你可以吃掉的苹果的最大数目。

输入：apples = [1,2,3,5,2], days = [3,2,1,4,2]

输出：7

来源：力扣（LeetCode）

链接：https://leetcode-cn.com/problems/maximum-number-of-eaten-apples

解答

贪心算法，即每次吃苹果的时候，都吃最快要过期的那一批苹果。

其次，使用优先队列priority_queue存储一对值，包括苹果的过期日子和苹果数量。

此外，吃苹果又可以分为两个时期：

每天还能收苹果（也可能为0）（0 - apple.size() - 1）
已经过了收苹果的日子了.(apple.size()+的日子)

第一时期:

收苹果，如果当天有苹果，就收苹果，并将苹果打包。存储其过期的日子和数量到有限队列中；
把坏的苹果扔掉，由于是优先队列，直接观察top()的苹果，如果其保质期已过，就pop()即可，一直循环到top()的苹果没坏；
取出top()的苹果，吃掉一个，数量-1，吃的数量+1，如果还剩下的>0，则再放回到队列中。

第二时期：

同第一时期的2+3步骤。

最终即可求得吃苹果的最大数目。

class Solution {
public:
    int eatenApples(vector<int> &apples, vector<int> &days) {
        int ret = 0;
        int n = static_cast<int>(apples.size());
        int i = 0; // 时间指针，第 i 天

        // 优先队列，将苹果打包打tag
        priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> p;

        // 0 - (n-1)天，每天都可能有新苹果
        for (i = 0; i < n; ++i) {
            // 有苹果才收苹果
            if (apples[i] > 0) {
                // 收苹果，存储 过期时间 + 数量
                p.push(pair<int, int>{i + days[i], apples[i]}); // x 为过期时间，y为数量
            }

            // 过期苹果扔掉
            while (!p.empty() && p.top().first <= i) {
                // 如果过期了，就淘汰
                p.pop();
            }

            // 有苹果能吃，就吃
            if (!p.empty()) {
                // 拿苹果
                auto eat = p.top();
                p.pop();

                // 吃苹果
                eat.second--;
                ret++;

                // 苹果剩下了才放回去
                if (eat.second > 0) {
                    p.push(eat);
                }
            }
        }

        // 剩下的日子，只要还有库存，就还能吃苹果
        while (!p.empty()) {
            // 吃苹果，挑不过期的
            while (!p.empty() && p.top().first <= i) {
                // 如果过期了，就淘汰
                p.pop();
            }

            // 有苹果能吃，就吃
            if (!p.empty()) {
                // 拿苹果
                auto eat = p.top();
                p.pop();

                // 吃苹果
                eat.second--;
                ret++;

                // 苹果剩下了才放回去
                if (eat.second > 0) {
                    p.push(eat);
                }
            }

            // 日子又过一天
            i++;
        }

        return ret;

    }
};

1705. 吃苹果的最大数目

题目

解答