补充知识

优先队列

• 在优先队列中，每一个元素都有一个优先级，优先级高的元素先得到服务
• 一个定义优先队列的例子：priority_queue<pii, vector<pii>, greater<pii>> pq;
  • 其中typedef pair<int, int> pii;
  • 这行代码声明了一个基于小顶堆（最小优先队列）的优先队列，即优先级最低的元素会排在队列顶端
  • 其中，pii表示这个pq优先队列中的元素都是这个类型的
  • 剩下的vector<pii>表示这个队列是基于vector实现的，greater<pii>> pq表示这个队列是按照从小到大进行排列的

实现代码

typedef pair<int, int> pii;


class Solution {
public:
    int eatenApples(vector<int>& apples, vector<int>& days) {
        int ans = 0;
        // 定义一个优先队列 pq，存储 pair<int, int> 类型的数据。
        // 1. 使用的底层容器为 vector<pii>。
        // 2. 比较方式为 greater<pii>，因此这是一个**最小堆**优先队列。
        //    - 队列中的元素按照字典序排序：
        //      a. 先比较 pair 的第一个值（first），值小的优先级高；
        //      b. 如果第一个值相等，再比较第二个值（second），值小的优先级高。
        // 3. 常用操作：
        //    a. pq.emplace(x, y)：插入一个 pair(x, y)；
        //    b. pq.top()：获取优先级最高（即最小）的元素；
        //    c. pq.pop()：移除优先级最高的元素。
        //
        // 示例：插入 (3, 2), (1, 5), (2, 4) 后，
        // 队列中的元素按顺序为 (1, 5), (2, 4), (3, 2)。    
        priority_queue<pii, vector<pii>, greater<pii>> pq;
        // 优先队列存储二元组，每个二元组表示苹果的腐烂日期和在该日期腐烂的苹果个数
        int n = apples.size();
        int i  = 0;
        // i表示当前日期为第i天
        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;
    }
};