题解 | 小苯的比赛上分

出题人真是神了

拿我noob109写的双端优先序列复制过来，然后根据题意编写一下主函数就可以了

#include <iostream>
#include <queue>
#include <vector>
using namespace std;

class double_ended_priority_queue
{
private:
//创建两个主堆

    //最小堆
    priority_queue<int,vector<int>,greater<int>> min_pq;
    //最大堆
    priority_queue<int> max_pq;


//创建两个待删除堆，用来记录需要从对方堆中删除的元素

    //最小堆删除堆
    priority_queue<int,vector<int>,greater<int>> min_to_delete;
    //最大堆删除堆
    priority_queue<int> max_to_delete;


//创建清除函数

    //最小堆清除函数，删除所有标记为待删除的堆顶元素
    void clean_min_pq()
    {
        //两个堆都不为空，同时堆顶元素相同
        while (!min_pq.empty() && !min_to_delete.empty() && min_pq.top() == min_to_delete.top())
        {
            min_pq.pop();
            min_to_delete.pop();
        }
    }

    //最大堆清除函数，删除所有标记为待删除的堆顶元素
    void clean_max_pq()
    {
        //两个堆都不为空，同时堆顶元素相同
        while (!max_pq.empty() && !max_to_delete.empty() && max_pq.top() == max_to_delete.top())
        {
            max_pq.pop();
            max_to_delete.pop();
        }
    }



public:
    //插入函数：将元素同时插入最大堆与最小堆
    void push(int x)
    {
        min_pq.push(x);
        max_pq.push(x);
    }


//创建获取函数

    //最小值获取函数
    int get_min()
    {
        clean_min_pq();  //先清除最小堆待删除元素，防止被获取
        if (min_pq.empty())
        {
            return -1;
        }
        //获取最小堆的顶部元素，即最小值
        int min_num = min_pq.top();
        return min_num;
    }

    //最大值获取函数
    int gei_max()
    {
        clean_max_pq();  //先清除最大堆待删除元素，防止被获取
        if (max_pq.empty()) 
        {
            return -1;
        }
        //获取最大堆顶部元素，即最大值
        int max_num = max_pq.top();
        return max_num;
    }


//创建删除函数

    //最小值删除函数
    void min_pop()
    {
        clean_min_pq();  //依旧先清理
        if (min_pq.empty())
        {
            return;
        }
        //获取要删除的值
        int num_to_delete = min_pq.top();
        //获取后从最小堆中删除
        min_pq.pop();
        //将获取的值加入最大堆待删除列表
        max_to_delete.push(num_to_delete);
    }

    //最大值删除函数
    void max_pop()
    {
        clean_max_pq(); //清理
        if (max_pq.empty())
        {
            return;
        }
        //获取要删除的值
        int num_to_delete = max_pq.top();
        //获取后从最大堆删除
        max_pq.pop();
        //将获取到的值加入最小堆待删除列表
        min_to_delete.push(num_to_delete);
    }


//检查队列是否为空 (这里也可以换成检测最大堆，两个是一样的)
    bool empty()
    {
        //先清理最小堆
        clean_min_pq();  
        //如果最小堆为空，则队列为空
        return min_pq.empty();
    }
};

int main() {
    int n = 0,m = 0;
    cin >> n >> m;
    //创建双端序列
    double_ended_priority_queue scores;
    //将所有账户分数放入双端序列
    for (int i = 0;i < n;i++)
    {
        int accout_score = 0;
        cin >> accout_score;
        scores.push(accout_score);
    }
    //开始比赛，依次处理
    for (int i = 0;i < m;i++)
    {
        //打完增加的分数
        int add_score = 0;
        cin >> add_score;
        //目前所有账户中最小的分数
        int min_score = scores.get_min();
        //获取后删去防干扰
        scores.min_pop();
        min_score += add_score;
        scores.push(min_score);
        cout << scores.gei_max() << "\n";
    }
    return 0;
}