题解：P12085 [蓝桥杯 2023 省 B] 整数删除

fish_love_cat · 2025-04-09 14:14:37 · 题解

可删堆会写吧？链表会写吧？那么做完了。

上面是我在通过此题前写的一句话题解。

然后发现小模拟调不出来，呜呜 /ll

首先要求动态最小值及其下标，可以利用堆来做。

注意可删堆同时要维护一个数据版本用于更新，每次遇到过期数据都要立刻扔掉。

然后对于每一个取出来的点，用链表维护出上下的点，然后对其更新。

对于不存在的点请不要处理。

直接模拟删除过程就做完了，注意要给删掉的点打标记。

#include<bits/stdc++.h>
#define int unsigned long long
using namespace std;
int n,k;
struct fish{
    int x,lst,nxt,id;
    int rk;
    bool operator <(fish a)const{
        if(x==a.x)return id>a.id;
        return x>a.x;
    }
}a[500005];
struct delete_Q{
    priority_queue<fish>q1,q2;
    void push(fish x){
        q1.push(x);
    }
    void pop(fish x){
        q2.push(x);
    }
    fish top(){
        while(!(a[q1.top().id].rk==q1.top().rk&&(q2.empty()||a[q2.top().id].rk==q2.top().rk&&q1.top().id!=q2.top().id))){
            while(a[q1.top().id].rk!=q1.top().rk)q1.pop();
            while(!q2.empty()&&a[q2.top().id].rk!=q2.top().rk)q2.pop();
            if(q2.empty())break;
            if(q1.top().id==q2.top().id)q1.pop(),q2.pop();
        }
        return q1.top();
    }
}q;
void del(fish x){
    if(x.lst!=0){
        fish flc=a[x.lst];
        q.pop(flc);
        flc.nxt=x.nxt;
        flc.x+=x.x;
        flc.rk++;
        a[flc.id]=flc;
        q.push(flc);
    }
    if(x.nxt!=n+1){
        fish flc=a[x.nxt];
        q.pop(flc);
        flc.lst=x.lst;
        flc.x+=x.x;
        flc.rk++;
        a[flc.id]=flc;
        q.push(flc);
    }
    a[x.id].x=-1;
}
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(),cout.tie();
    cin>>n>>k;
    for(int i=1;i<=n;i++)
    cin>>a[i].x,a[i].lst=i-1,a[i].nxt=i+1,a[i].id=i,a[i].rk=0,q.push(a[i]);
    while(k--){
        fish flc=q.top();
        q.pop(flc);
        del(flc);
    }
    for(int i=1;i<=n;i++)
    if(a[i].x!=-1)cout<<a[i].x<<' ';
    return 0;
}

截至目前运行时长位列倒二，人傻常数大。