题目大意

依次删除长度为 $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;
}

【在线测评】