原题链接:整数删除
给定一个长度为 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;
}