蓝桥杯真题 - 整数删除 - 题解

题目链接：https://www.lanqiao.cn/problems/3515/learning/

个人评价：难度 2 星（满星：5）
前置知识：STL

整体思路

• 本题需要做到：快速找到值最小且下标最小的元素，快速删除某个位置的元素；
• 可以用优先队列 $O(\log n)$ 找到最小元素，用并查集或者链表模拟 $O(1)$ 删除操作，优先队列中每个元素维护值、下标、链表迭代器（如果用并查集的话就不需要存迭代器了），再用一个额外数组存更新后的数组值，由于优先队列在数组内元素修改时无法及时更新堆内元素，可以在出队时判断队列中的值是否为最新值（用 vis 数组标记是否被更新过），如果是最新值则更新相邻数字，否则将最新值加入优先队列重新查找最小值。

过题代码

#include <bits/stdc++.h>
using namespace std;

typedef long long LL;
const int maxn = 500000 + 100;
struct Node {
    LL num;
    int idx;
    list<int>::iterator it;

    Node() {}
    Node(LL num, int idx, list<int>::iterator it) : num(num), idx(idx), it(it) {}
};

bool operator<(const Node &a, const Node &b) {
    return a.num == b.num ? a.idx > b.idx : a.num > b.num;
}

int n, k;
LL num[maxn];
bool vis[maxn];
list<int> lst;
list<int>::iterator it;
priority_queue<Node> que;

int main() {
#ifdef ExRoc
    freopen("test.txt", "r", stdin);
#endif // ExRoc
    ios::sync_with_stdio(false);

    cin >> n >> k;
    for (int i = 1; i <= n; ++i) {
        cin >> num[i];
        lst.push_back(i);
        it = lst.end();
        --it;
        que.push(Node(num[i], i, it));
    }
    while (k > 0) {
        Node node = que.top();
        que.pop();
        if (vis[node.idx]) {
            vis[node.idx] = false;
            node.num = num[node.idx];
            que.push(node);
            continue;
        }

        --k;
        if (node.it != lst.begin()) {
            it = node.it;
            --it;
            num[*it] += num[node.idx];
            vis[*it] = true;
        }

        it = node.it;
        ++it;
        if (it != lst.end()) {
            num[*it] += num[node.idx];
            vis[*it] = true;
        }
        lst.erase(node.it);
    }
    for (int idx : lst) {
        cout << num[idx] << " ";
    }
    cout << endl;

    return 0;
}