题解：P16276 [蓝桥杯 2026 省 C] 回收处理

· · 题解

扫一遍过去，同时对前缀和后缀开一个堆，然后容易发现你需要支持插入和删除。

直接上可删堆即可，维护堆内元素和做完了。

可删堆的实现原理就是，用一个堆维护删除堆，一个堆维护加入堆，如果堆顶相同就一起弹出实现删除，时间复杂度一样是 O(n\log n) 的。

用 map 对元素标记可以做到一样的效果其实，不管了很久以前封装过这个玩意直接拿来用。

代码还没写明天来补。
补完了。

#include<bits/stdc++.h>
#define int long long
using namespace std;
struct delete_Q{
    priority_queue<int>q1,q2;
    int op;
    delete_Q(int x=1){op=x;}
    void push(int x){
        x*=op;
        q1.push(x);
    }
    void pop(int x){
        x*=op;
        q2.push(x);
    }
    void rebuild(){
        priority_queue<int>flc;
        while(!q1.empty())
        if(!q2.empty()&&q1.top()==q2.top())q1.pop(),q2.pop();
        else flc.push(q1.top()),q1.pop();
        q1=flc;
    }
    bool empty(){
        while(!q2.empty()&&q1.top()==q2.top())q1.pop(),q2.pop();
        return q1.empty();
    }
    int size(){
        if(empty())return 0;
        if(q1.size()<q2.size())exit(75);
        return q1.size()-q2.size();
    }
    int top(){
        if(empty())exit(75);
        return op*q1.top();
    }
    void pop(){
        pop(top());
    }
}q1(-1),q2(1),q3(-1);
int a[300005];
signed main(){
    int n;
    cin>>n;
    int cnt1=0,cnt2=0;
    for(int i=1;i<=n*3;i++){
        cin>>a[i];
        if(i>n)q2.push(a[i]),cnt2+=a[i];
        else q1.push(a[i]),cnt1+=a[i];
    }
    while(q2.size()>n)
    cnt2-=q2.top(),
    q3.push(q2.top()),
    q2.pop();
    int ans=cnt1-cnt2;
    for(int i=n+1;i<=n*2;i++){
        if(a[i]<=q2.top())
        cnt2-=a[i],q2.pop(a[i]),
        cnt2+=q3.top(),q2.push(q3.top()),q3.pop();
        else q3.pop(a[i]);
        if(a[i]>q1.top())
        cnt1-=q1.top(),q1.pop(),
        cnt1+=a[i],q1.push(a[i]);
        ans=max(ans,cnt1-cnt2);
    }
    cout<<ans;
    return 0;
}
//「可爱！可爱！」
// 莉艾儿拍拍手，感到很开心。

// 潘丽宝一边揉乱莉艾儿的头发（结果被讨厌了），一边追着自己拉得长长的影子，踏上回家的道路。