1705.吃苹果的最大数目

问题描述

1705.吃苹果的最大数目 中等

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天之后再进行单独判断

代码

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;
    }
};