网站防止被采集,商务网站建设与维护补考试卷,百度网站排名软件,wordpress 网站访问量原题链接#xff1a;整数删除
给定一个长度为 N 的整数数列#xff1a;A1,A2,...,AN。
你要重复以下操作 K 次#xff1a;
每次选择数列中最小的整数#xff08;如果最小值不止一个#xff0c;选择最靠前的#xff09;#xff0c;将其删除#xff0c;并把与它相邻的…原题链接整数删除
给定一个长度为 N 的整数数列A1,A2,...,AN。
你要重复以下操作 K 次
每次选择数列中最小的整数如果最小值不止一个选择最靠前的将其删除并把与它相邻的整数加上被删除的数值。
输出 K 次操作后的序列。
输入格式
第一行包含两个整数 N 和 K。
第二行包含 N 个整数A1,A2,A3,...,AN。
输出格式
输出 N−K个整数中间用一个空格隔开代表 K 次操作后的序列。
数据范围
对于 20% 的数据1≤KN≤10000。 对于 100% 的数据1≤KN≤5×10^50≤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-- 代码实现
#includeiostream
#includequeue
#define int long long
using namespace std;
const int N5e55;
typedef pairint,int PII;
struct{int pre,num,next;//pre前一个下标next后一个下标num当前值
}a[N];
int n,k;
signed main(){priority_queuePII,vectorPII,greaterPII pq;//小根堆cinnk;for(int i1;in;i){cina[i].num;a[i].prei-1;//记录前驱a[i].nexti1;//记录后驱pq.push(make_pair(a[i].num,i));//把此点数值与下标入队}while(k){//删除k个数PII curpq.top();//小根堆每次弹出都是最小值pq.pop();int idcur.second,wcur.first;//记录弹出的下标与值int la[id].pre,ra[id].next;//记录前后驱if(w!a[id].num){//如果队列中的值与原数组更新后的不相等pq.push(make_pair(a[id].num,id));//把新值入队continue;//k不动更新操作}//else就是删除更新操作k--;a[l].numw;//前一个加wa[r].numw;//后一个加wa[l].nextr;//双端队列删除id结点a[r].prel;a[id].num0;//删掉了为0}for(int i1;in;i){if(a[i].num){couta[i].num ;}}return 0;
}
