【LeetCode每日一题】1705. 吃苹果的最大数目【优先队列+贪心】

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

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

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

示例 1：

输入：apples = [1,2,3,5,2], days = [3,2,1,4,2] 输出：7 解释：你可以吃掉 7 个苹果：

• 第一天，你吃掉第一天长出来的苹果。
• 第二天，你吃掉一个第二天长出来的苹果。
• 第三天，你吃掉一个第二天长出来的苹果。过了这一天，第三天长出来的苹果就已经腐烂了。
• 第四天到第七天，你吃的都是第四天长出来的苹果。 示例 2：

输入：apples = [3,0,0,0,0,2], days = [3,0,0,0,0,2] 输出：5 解释：你可以吃掉 5 个苹果：

• 第一天到第三天，你吃的都是第一天长出来的苹果。
• 第四天和第五天不吃苹果。
• 第六天和第七天，你吃的都是第六天长出来的苹果。  

提示：

apples.length == n days.length == n 1 <= n <= 2 * 104 0 <= apples[i], days[i] <= 2 * 104 只有在 apples[i] = 0 时，days[i] = 0 才成立

题解： 这道题写得时候感觉没有完全想好就开始写了，一开始想到的就是用优先队列，但是后来又觉得可能会加入很多重复的元素，影响效率，就改了一种写法，结果发现怎么写都写得不舒畅，写了一个n2复杂度的，还不如用一个优先队列去做。。。 基本思想就是：将当前这一天结出的果实放到队列当中，然后从队列当中先除掉已经腐烂的果实，然后取出队首的果实，将数量减一之后再放入队列（如果这包果实刚好为1，就不放了）。当数组遍历完毕后，就直接将队列中的果实依次取出，此时答案可以作差计入，不需要一个个加了。

typedef pair<int,int> pii;

class Solution {
public:
    int eatenApples(vector<int>& apples, vector<int>& days) {
        int ans = 0;
        priority_queue<pii, vector<pii>, greater<pii>> pq;
        int n = apples.size();
        int i = 0;
        while (i < n) {
            while (!pq.empty() && pq.top().first <= i) {
                pq.pop();
            }
            int rottenDay = i + days[i];
            int count = apples[i];
            if (count > 0) {
                pq.emplace(rottenDay, count);
            }
            if (!pq.empty()) {
                pii curr = pq.top();
                pq.pop();
                curr.second--;
                if (curr.second != 0) {                  
                    pq.emplace(curr.first, curr.second);
                }
                ans++;
            }
            i++;
        }
        while (!pq.empty()) {
            while (!pq.empty() && pq.top().first <= i) {
                pq.pop();
            }
            if (pq.empty()) {
                break;
            }
            pii curr = pq.top();
            pq.pop();
            int num = min(curr.first - i, curr.second);
            ans += num;
            i += num;
        }
        return ans;
    }
};