第十四届蓝桥杯省赛大学B组(C/C++)整数删除

原题链接:整数删除

给定一个长度为 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;
}
上一篇:记录一下做工厂的打印pdf程序


下一篇:Tuxera NTFS for Mac2023绿色免费版 免费的ntfs for mac 免费读写硬盘U盘工具-Tuxera NTFS for Mac2023绿色版安装包(一键安装):https://sourl.cn/mJu6Uf