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

· · 题解

朴素思路

首先我们根据题意模拟出朴素思路：每次操作时，

找到最小数：遍历数组，找到最小中最靠前的数，记录 flag_i 表示 A_i 是否已经被删除；删除：标记 flag_i 的值；修改操作：往左边和右边寻找相邻数加上自身权值。

时间复杂度为 O(nk)，无法接受。

第一步优化

最外层的 O(k) 显然已经无法优化，考虑优化每次操作，即内层。为了偷懒方便叙述，下文复杂度皆为单次操作的时间复杂度。

对于第一步，找到最小中最可靠前的数，遍历的时间复杂度为 O(n)，而我们如果记录一个优先队列来维护数组中未被删除的元素中最小且最靠前的数，就能将这一步优化到 O(\log n)。

对于第二步，我们的操作便是弹出队首即可。时间复杂度为 O(1)。

对于第三步，如何快速找到左右两边未被删除的相邻数？分析问题，我们发现需要一种支持快速删除以及快速前后查找的数据结构——链表。

于是我们一开始维护一个双向链表，初始时 i 的 left 指向 i-1，i 的 right 指向 i+1。每次删除节点时，将节点左边与右边相连即可。

于是我们做到了 O(1) 左右寻找与删除。

最后一步优化

注意到第三步操作中，我们需要把 left 和 right 修改后的权值加入优先队列，这很方便。

然而，我们需要将队列中 left 和 right 原来的权值删除，这需要遍历整个优先队列去查找，时间复杂度 O(n)，功亏一篑。

遇到这种情况，我们先无脑将新权值加入队列，再想这个问题。

有没有什么简便的方法知道区分队列中相同 i 对应权值的新旧性？

我们对每个加入的权值记录一个变量，表示这个权值的版本。越后操作修改的权值版本越新，同时我们记录全局数组 version_i 表示 A_i 的版本，这样，对于队列的每个队首，我们只需判断队首权值的版本是否与全局版本一致，单次判断时间复杂度 O(1)。

至此，本题全部结束。总时间复杂度为 O(n\log n)。

以下为代码。

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 500005;
int n, k;
ll a[N];
struct List {
    int l, r;
} lst[N]; // 链表的维护
struct Node {
    int id;
    ll val;
    int vrs; // 天才做法！定义数据版本！
    bool operator < (const Node cmp) const {
        return (val == cmp.val ? id > cmp.id : val > cmp.val);
    }
};
priority_queue <Node> pq; // 优先队列，维护最小值
int version[N]; 
bool flag[N];
int main(void) {
    cin.tie(0), cout.tie(0);
    cin >> n >> k;
    for (int i = 1; i <= n; ++i) {
        cin >> a[i];
        pq.push((Node){i, (ll)a[i], 0});
        lst[i].l = i-1, lst[i].r = i+1; // 链表的初始化
    }
    lst[1].l = lst[n].r = -1;
    for (int tim = 1; tim <= k; ++tim) { // 版本迭代
        while (!pq.empty() && pq.top().vrs != version[pq.top().id]) pq.pop(); // 弹出旧数据
        Node top = pq.top();
        pq.pop();
        int id = top.id;
        flag[id] = true; // 标记是否被删除
        ll val = top.val;
        int left = lst[id].l, right = lst[id].r;
        if (left != -1) { // 记得特判
            lst[left].r = right;
            a[left] += val;
            pq.push((Node){left, a[left], tim});
            version[left] = tim; // 更新版本
        }
        if (right != -1) { // 记得特判！
            lst[right].l = left;
            a[right] += val;
            pq.push((Node){right, a[right], tim});
            version[right] = tim; //  更新版本
        }
    }
    for (int i = 1; i <= n; ++i) {
        if (!flag[i]) {
            cout << a[i] << ' ';
        }
    }
    return 0;
}

别忘记点个赞呀。