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

jaiy_cqg · 2025-05-31 17:10:13 · 题解

思路

把初始元素保存成 val,id 的结构体变量，放入优先队列，每次从优先队列弹出最小值，看它是否和结构体中的 val 一致，如果一致说明是新的，否则跳过根据它的 id 找到左边和右边，加和，更新结构体中的值，放入优先队列。

做法

双向链表 l 和 r 维护相邻关系优先队列实现最小堆，自定义比较运算符处理相同值情况。初始化时建立双向链表连接。每次从堆顶取出有效最小值（跳过已删除元素），更新左右邻居的值并调整链表结构，将更新后的邻居重新入堆。最后遍历存活节点时通过链表指针跳转，自动跳过被删除的节点。

代码

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 5e5 + 10;

struct node {
    ll val;//值
    int id;//下标
} a[N];
priority_queue<node>q;
int l[N], r[N], n, m;

int vis[N];//表示某个节点是否被删掉
bool operator < (node other, node top) {
    //按val小的优先，val相等按id小的优先
    if (other.val == top.val)
        return top.id < other.id;
    return top.val < other.val;
}

int main() {
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        cin >> a[i].val;
        a[i].id = i;
        q.push(a[i]);
    }

    //0作为头结点，n+1作为尾节点
    r[0] = 1, l[n + 1] = n;
    for (int i = 1; i <= n; i++) {//双向链表初始化
        l[i] = i - 1, r[i] = i + 1;
    }
    while (m--) { //      根据下标找到的val和队列的val不一致 或已经被删除过了
        while (a[q.top().id].val != q.top().val || vis[q.top().id]) {
            q.pop();
        }
        auto p = q.top().id; //这个一定是最新的
    //    cout << a[p].val << "<-val \n";
        q.pop();
        int left = l[p], right = r[p];
        a[left].val += a[p].val, a[right].val += a[p].val; //左右加和
        vis[p] = 1;
        r[left] = right, l[right] = left; //链表的更新
        if (left >= 1)
            q.push(a[left]);//不是虚拟节点
        if (right <= n)
            q.push(a[right]);//不是虚拟节点
    }
    int p = r[0];
    while (p != n + 1) {
        cout << a[p].val << " ";
        p = r[p];
    }
}