# 1705.吃苹果的最大数目

## 问题描述
[1705.吃苹果的最大数目](https://leetcode.cn/problems/maximum-number-of-eaten-apples/) **中等**

There is a special kind of apple tree that grows apples every day for `n` days. On the `ith` day,
the tree grows `apples[i]` apples that will rot after `days[i]` days, that is on day `i + days[i]`
the apples will be rotten and cannot be eaten. On some days, the apple tree does not grow any
apples, which are denoted by `apples[i] == 0` and `days[i] == 0`.
You decided to eat **at most** one apple a day (to keep the doctors away). Note that you can keep
eating after the first `n` days.
Given two integer arrays `days` and `apples` of length `n`, 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
Explanation: You can eat 7 apples:
- On the first day, you eat an apple that grew on the first day.
- On the second day, you eat an apple that grew on the second day.
- On the third day, you eat an apple that grew on the second day. After this day, the apples that
grew on the third day rot.
- On the fourth to the seventh days, you eat apples that grew on the fourth day.
```
**Example 2:**
```
Input: apples = [3,0,0,0,0,2], days = [3,0,0,0,0,2]
Output: 5
Explanation: You can eat 5 apples:
- On the first to the third day you eat apples that grew on the first day.
- Do nothing on the fouth and fifth days.
- On the sixth and seventh days you eat apples that grew on the sixth day.
```
**Constraints:**
- `n == apples.length == days.length`
- `1 <= n <= 2 * 10⁴`
- `0 <= apples[i], days[i] <= 2 * 10⁴`
- `days[i] = 0` if and only if `apples[i] = 0`.

## 解题思路
吃苹果的最佳策略就是，每次只吃最先腐烂的苹果，即吃腐烂日期最小的苹果，利用优先队列来模拟这个过程。

`vector<vector<int>> app_decay(apples.size(), vector<int>(2, 0))`; 
`app_decay[i][0]`表示第`i`天结出的苹果的预计腐烂时间，`app_decay[i][1]`表示第`i`天结出了多少个苹果。

优先队列的`top()`必须是腐烂时间最小的`app_decay[i]`

按时间遍历，如果当天结出了苹果，就将其加入优先队列`pq`，然后弹出堆顶元素直到堆为空或者`pq.top()[0] > i`，然后将`pq.top()[1]--`。

`n`天之后再进行单独判断

## 代码
```cpp
class Solution {
  public:
    int eatenApples(vector<int> &apples, vector<int> &days) {
        // 优先吃最早腐烂的苹果，即吃腐烂日期最小的苹果
        vector<vector<int>> app_decay(apples.size(), vector<int>(2, 0));
        for (int i = 0; i < apples.size(); i++) {
            app_decay[i][0] = i + days[i];
            app_decay[i][1] = apples[i];
        }
        priority_queue<vector<int>> q;
        auto cmp = [&](vector<int> &v1, vector<int> &v2) {
            return v1[0] >= v2[0];
        };
        // 优先队列的top应该是腐烂日期最小的
        priority_queue<vector<int>, vector<vector<int>>, decltype(cmp)> pq(cmp);
        int res = 0;
        for (int i = 0; i < apples.size(); i++) {
            if (app_decay[i][1] != 0) {
                pq.push(app_decay[i]);
            }
            vector<int> vec;
            while (!pq.empty() && pq.top()[0] <= i) {
                pq.pop();
            }
            if (!pq.empty()) {
                vec = pq.top();
                pq.pop();
            }
            if (!vec.empty() && vec[0] > i) {
                vec[1]--;
                if (vec[1] != 0) {
                    pq.push(vec);
                }
                res++;
            }
        }
        int date = apples.size();
        while (!pq.empty()) {
            vector<int> vec1;
            while (!pq.empty() && pq.top()[0] <= date) {
                pq.pop();
            }
            if (!pq.empty()) {
                vec1 = pq.top();
                pq.pop();
            }
            if (!vec1.empty() && vec1[0] > date) {
                vec1[1]--;
                if (vec1[1] != 0)
                    pq.push(vec1);
                res++;
            }
            date++;
        }
        return res;
    }
};
```