給定一個長度為N的整數數列A_1,A_2,...,A_N，請重復以下操作K次。

每次選擇數列中最小的整數（如果最小值不止一個，選擇最靠前的），將其刪除，并把與它相鄰的整數加上被刪除的數值。

請問K次操作后的序列是什么。

?

數列分別由鏈表和優先隊列來處理：
1）鏈表。把數列存到鏈表的節點上，在鏈表上刪除最小值節點，并且更新它的鄰居，是加上被刪除的節點的值。最小值是通過優先隊列找到的。
2）優先隊列。把數列存到優先隊列中，每次操作取出最小值。然后把更新后的數重隊列。
3）優先隊列找到最小值后，用優先隊列找最小值t，t對應的鏈表節R[t]。

?

#include <bits/stdc++.h>

using namespace std;

const int N = 5e5 + 10;

long long v[N]; //數列的值相加后可能超過int,需要用long long

int L[N], R[N]; //雙向鏈表

void del(int x) { //雙向鏈表:刪除x節點

? ? R[L[x]] = R[x], L[R[x]] = L[x]; //刪除第x個節點

? ? v[L[x]] += v[x], v[R[x]] += v[x]; //更新左、右鄰居

}

int main() {

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

? ? //優先隊列，優先隊列的元素是{權值,節點下標}

? ? priority_queue< pair<long long, int>, vector< pair<long long, int>>,

? ? ? ? ? ? ? ? ? ?greater< pair<long long, int>> > Q;

? ? //輸入并構造雙向鏈表

? ? R[0] = 1; //隊頭0,右指針R[0]指向節點1

? ? L[n + 1] = n; //隊尾n+1,左指針L[N+1]指向節點n

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

? ? ? ? cin >> v[i]; //讀數列

? ? ? ? L[i] = i - 1, R[i] = i + 1; //構造雙向鏈表,第i個節點表示v[i]

? ? ? ? Q.push({v[i], i}); //把數列放進優先隊列,求最小值

? ? }

? ? while (k--) { //k次操作

? ? ? ? auto p = Q.top();?

? ? ? ? //讀優先隊列的隊頭,隊頭是最小值.p.first是值,p.second是它的位置

? ? ? ? Q.pop(); //彈走隊頭,優先隊列會重新排序,新的隊頭仍是最小值

? ? ? ? if (p.first != v[p.second]) { //這個隊頭被del()改過了,不一定最小

? ? ? ? ? ? Q.push({v[p.second], p.second}); //重新放進隊列,重新排序

? ? ? ? ? ? k++; //撤銷這次操作

? ? ? ? }

? ? ? ? else del(p.second); //刪除節點并更新鄰居

? ? }

? ? int t = R[0]; //隊頭0,R[0]指向第一個數

? ? while (t != n + 1) { //遍歷鏈表

? ? ? ? cout << v[t] << " "; //輸出鏈表元素

? ? ? ? t = R[t];

? ? }

? ? return 0;

}