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

· · 题解

本题的优秀题解有很多，大致思路是用双向链表储存数列，方便进行加值操作，再用优先队列维护 A 中最小值，在相邻数加值并入队后利用懒标记，排除掉过期的数据。在这里笔者不详细解释，而是想给大家总结一下解题过程中的难点、注意事项和方法。某种程度上代替了警示后人

part 1.思维难点

这道题目的核心难点在于，通过维护一个数据版本来判断优先队列中的数据能不能用。相信很多人做题时，能顺利想到用优先队列维护 A 中最小值，但问题在于如何判断新入队的修改后的数，和以前入队的旧的数。这里用到了标记数据版本这个 trick，巧妙且有用，应该牢记住。

part 2.代码实现注意

我看身边挺多人被代码实现卡过，因此痛批蓝桥杯。

  1. 最常提的，不开 long long 见祖宗，因为本题的 A_i 加值后最大能达到 5\times10^{13}。
  2. 在给左右两边的数加值时，注意判断链表的边界情况，不然你就会得到 UB 和 TLE。
  3. 写双向链表这玩意，要注意分清左右，不要搞混了，感觉实在调不出来，可以试试直接重写，思路更清晰。

part 3.总结

写题多注意数据的可能上限。写链表小心边界，注意实现。不长的代码调不出不要死扣，试试重写。记住维护数据版本这种队列的小 trick。

感谢 @cuberYida、@rekcA_h 为文章提供的意见，附上不怎么好看的代码。

::::info[code]

#include<bits/stdc++.h>
#define co const 
#define lx x<<1
#define rx x<<1|1
#define ll long long
#define pii pair<int,int>
#define pll pair<long long,long long>
using namespace std;
co int N=5e5+5;
int n,k,bh[N],fl[N];
ll a[N];
struct List{
    int l,r;
}lst[N];
struct node{
    int id;
    int b;
    ll val;
    bool operator < (const node cmp) const{
        return val==cmp.val?id>cmp.id:val>cmp.val;
    }
};
priority_queue<node> q;
int main() {
    cin>>n>>k;
    for(int j=1; j<=n; j++){
        cin>>a[j];
        q.push({j,0,a[j]});
        lst[j].l=j-1,lst[j].r=j+1;
    }
    for(int j=1; j<=k; j++){
        while(!q.empty() && q.top().b!=bh[q.top().id]) q.pop();
        int x=q.top().id;
        fl[x]=1;
        q.pop();
        if(lst[x].l>=1){
            lst[lst[x].l].r=lst[x].r;
            bh[lst[x].l]=j;
            a[lst[x].l]+=a[x];
            q.push({lst[x].l,j,a[lst[x].l]});
        }
        if(lst[x].r<=n){
            lst[lst[x].r].l=lst[x].l;
            bh[lst[x].r]=j;
            a[lst[x].r]+=a[x];
            q.push({lst[x].r,j,a[lst[x].r]});
        }
    }
    for(int j=1; j<=n; j++){
        if(!fl[j]) cout<<a[j]<<' ';
    }
    return 0;
}

::::