[蓝桥杯2023年第十四届省赛真题-整数删除] 双链表+小根堆

解题思路:

考虑到要动态维护最小值，所以用小根堆和双向链表来维护，而且堆顶元素可能因为被相加而变成不是最小，所以还要判断一下是否大小改变，如果有改变把新的值重新放入堆中，依次操作直到找到最小值。

注意事项：

开long long

参考代码:

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int N = 500010;

typedef pair<ll, int> PII;

priority_queue<PII, vector<PII>, greater<PII> > heap;

ll e[N], l[N], r[N];

int k, n;

void delect(int k) {

    l[r[k]] = l[k];

    r[l[k]] = r[k];

    e[r[k]] += e[k];

    e[l[k]] += e[k];

}

int main(void) {

    scanf("%d%d", &n, &k);

    r[0] = 1, l[n + 1] = n;

    for (int i = 1; i <= n; i++) {

        int x;

        scanf("%d", &x);

        e[i] = x, l[i] = i - 1, r[i] = i + 1;

        heap.push({x, i});

    }

    while (k--) {

        auto t = heap.top();

        heap.pop();

        if (t.first != e[t.second]) heap.push({e[t.second], t.second}), k++;

        else delect(t.second);

    }

    for (int i = r[0]; i != n + 1; i = r[i]) {

        printf("%lld ", e[i]);

    }

    return 0;

}