第十四届蓝桥杯省赛C++B组H题【整数删除】题解（AC）

题目大意

依次删除长度为 $n$ 的数组中的 $k$ 个最小值，在删除一个数后，该数的相邻数加上它的值，输出最终数组。

解题思路

数组中删除一个数的复杂度为 $O(n)$，故我们可以考虑用链表进行维护，这样删除一个数的时间复杂度为 $O(1)$。

在一个无序数组中查找最小值，我们可以考虑将数组的元素都放进堆里。

删除一个数时，会导致其相邻的数增加，要修改堆中任意位置的元素较为困难，但删除堆顶元素较为简单（先取堆顶元素，修改后再放回堆中），故当要增加某个元素的值时，我们可以对该数进行标记，待该点成为堆顶时，出队修改后放回。

综上，当要删除一个最小值时，可以从堆顶取出一个元素

• 若该点已经被删除了，则跳过。
• 若该点需要增加，则取出，修改后放回堆中，并跳过。
• 删除该点，并标记左右点。

AC_Code

#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>

using namespace std;

typedef long long LL;

const int N = 5e5 + 10;

int n, m;
LL w[N];
int l[N], r[N];
bool st[N];
struct Node
{
    LL v;
    int p;
    bool operator< (const Node& t) const
    {
        if (v != t.v)
            return v > t.v;
        return p > t.p;
    }
};
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    
    cin >> n >> m;
    for (int i = 1; i <= n; ++ i )
        cin >> w[i];
    for (int i = 1; i <= n; ++ i )
        l[i] = i - 1, r[i] = i + 1;
    l[1] = -1, r[n] = -1;

    priority_queue<Node> heap;
    for (int i = 1; i <= n; ++ i )
        heap.push({w[i], i});

    memset(w, 0, sizeof w);

    int cnt = 0;
    while (cnt < m)
    {
        auto t = heap.top();
        heap.pop();

        auto v = t.v;
        auto p = t.p;

        if (st[p])
            continue;

        if (w[p])
        {
            heap.push({v + w[p], p});
            w[p] = 0;
            continue;
        }

        int lp = l[p], rp = r[p];
        if (~lp)
            w[lp] += v;
        if (~rp)
            w[rp] += v;
        st[p] = true;
        r[lp] = r[p];
        l[rp] = l[p];
        cnt ++;
    }

    while (heap.size())
    {
        auto t = heap.top();
        heap.pop();

        auto v = t.v;
        auto p = t.p;

        if (st[p])
            continue;

        w[p] += v;
    }

    for (int i = 1; i <= n; ++ i )
        if (!st[i])
            cout << w[i] << ' ';
    cout << endl;

    return 0;
}

【在线测评】