原题链接：整数删除
给定一个长度为 N 的整数数列：A1,A2,...,AN。
你要重复以下操作 K 次：
每次选择数列中最小的整数（如果最小值不止一个，选择最靠前的），将其删除，并把与它相邻的整数加上被删除的数值。
输出 K 次操作后的序列。
输入格式
第一行包含两个整数 N 和 K。
第二行包含 N 个整数，A1,A2,A3,...,AN。
输出格式
输出 N−K个整数，中间用一个空格隔开，代表 K 次操作后的序列。
数据范围
对于 20% 的数据，1≤K<N≤10000。 对于 100% 的数据，1≤K<N≤5×10^5，0≤Ai≤10^8。
输入样例：
代码语言：javascript复制5 3
1 4 2 8 7输出样例：
代码语言：javascript复制17 7样例解释
数列变化如下，中括号里的数是当次操作中被选择的数：
代码语言：javascript复制[1] 4 2 8 7
5 [2] 8 7
[7] 10 7
17 7解题思路：
此题主要用优先队列 双端链表，优先队列可以替换成能够进行排序的也可，比如set（去重 自动排序），这里利用优先队列实现。利用小根堆，每次弹出来为最小值去更新原数组的值。这里需要判断一下，由于更新值在原数组中更新，优先队列中的值没有被更新，每次进入循环，先要进行判断原数组的值是否与优先队列中的值相等，不相等就更新，相等就按照删除继续操作，k--
代码实现：
代码语言：javascript复制#include<iostream>
#include<queue>
#define int long long
using namespace std;
const int N=5e5 5;
typedef pair<int,int> PII;
struct{
int pre,num,next;//pre前一个下标，next后一个下标，num当前值
}a[N];
int n,k;
signed main(){
priority_queue<PII,vector<PII>,greater<PII>> pq;//小根堆
cin>>n>>k;
for(int i=1;i<=n;i ){
cin>>a[i].num;
a[i].pre=i-1;//记录前驱
a[i].next=i 1;//记录后驱
pq.push(make_pair(a[i].num,i));//把此点数值与下标入队
}
while(k){//删除k个数
PII cur=pq.top();//小根堆，每次弹出都是最小值
pq.pop();
int id=cur.second,w=cur.first;//记录弹出的下标与值
int l=a[id].pre,r=a[id].next;//记录前后驱
if(w!=a[id].num){//如果队列中的值与原数组更新后的不相等
pq.push(make_pair(a[id].num,id));//把新值入队
continue;//k不动，更新操作
}//else就是删除更新操作
k--;
a[l].num =w;//前一个加w
a[r].num =w;//后一个加w
a[l].next=r;//双端队列删除id结点
a[r].pre=l;
a[id].num=0;//删掉了为0
}
for(int i=1;i<=n;i ){
if(a[i].num){
cout<<a[i].num<<" ";
}
}
return 0;
}
