1705 吃苹果的最大数目

题目链接

1705. 吃苹果的最大数目

分析

贪心+最小堆

由题意可得，最优的解法是吃会更先腐烂的苹果

使用最小堆维护苹果腐烂的日期和个数

对于 $n$ 天后的情况，我们可以不用一个一个模拟，每次从堆中拿出最先腐烂的那堆苹果，计算可以吃的个数，一次性解决即可

代码实现

class Solution {
public:
    int eatenApples(vector<int>& apples, vector<int>& days) {
        int n = days.size();
        int i = 0;
        int ans = 0;
        priority_queue<pair<int, int>, vector<pair<int, int>>, greater<> > pq;

        for(i = 0; i < n; ++i) {
            if(i < n && apples[i]) {
                pq.push({i + days[i], apples[i]});
            }

            while(!pq.empty() && (pq.top().first <= i || !pq.top().second)) {
                pq.pop();
            }

            if(!pq.empty()) {
                auto [x, y] = pq.top();
                pq.pop();
                pq.push({x, y - 1});
                ans++;
            }
        }

        while(1) {
            while(!pq.empty() && pq.top().first <= i) {
                pq.top();
            }
            if(pq.empty())
                break;

            auto [x, y] = pq.top();
            pq.pop();
            int t = min(y, x - i);
            i += t;
            ans += t;
        }

        return ans;
    }
};

复杂度分析

• 时间复杂度：$O(n\log n)$
• 空间复杂度：$O(n)$