蓝桥杯2023年第十四届省赛真题-整数删除

解题思路:

注意事项:

参考代码:

#include<iostream>

#include<queue>

#include<vector>

using namespace std;

using ll = long long;

const int N = 5e5 + 10;

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

//l[i]代表i下标的左边下标，r[i]代表i下标的右边下标,v[i]是i下标的值

void del(int x) {

    r[l[x]] = r[x], l[r[x]] = l[x];

    v[l[x]] += v[x], v[r[x]] += v[x];

}

//把id右边个体的左编号改为id的左编号

//把id左边个体的右编号改为id的右编号

int main () {

    int n, k; cin >> n >> k;

    priority_queue<pair<ll, int>, vector<pair<ll, int>>, greater<pair<ll, int>>> h;

    //输入并构造双向递增链表

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

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

        cin >> v[i], l[i] = i - 1, r[i] = i + 1, h.push({v[i], i});

    while (k --) {

        auto p = h.top(); h.pop();

        //如果v发生变化， 则目前的元素不一定是最小值， 需要重新放入堆中

        if (p.first != v[p.second]) h.push({v[p.second], p.second}), k ++;

        else del(p.second);

    }

    //输出链表剩余的元素

    int head = r[0];

    while (head != n + 1) {

        cout << v[head]<< " ";

        head = r[head];

    }

    return 0;

}