原题链接：整数删除
给定一个长度为 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。
输入样例：
5 3 1 4 2 8 7
输出样例：
17 7
样例解释
数列变化如下，中括号里的数是当次操作中被选择的数：
[1] 4 2 8 7 5 [2] 8 7 [7] 10 7 17 7
解题思路：
此题主要用优先队列+双端链表，优先队列可以替换成能够进行排序的也可，比如set（去重+自动排序），这里利用优先队列实现。利用小根堆，每次弹出来为最小值去更新原数组的值。这里需要判断一下，由于更新值在原数组中更新，优先队列中的值没有被更新，每次进入循环，先要进行判断原数组的值是否与优先队列中的值相等，不相等就更新，相等就按照删除继续操作，k--
代码实现：
#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; }
