【小根堆+双链表】蓝桥杯第十四届--整数删除

本文主要是介绍【小根堆+双链表】蓝桥杯第十四届--整数删除，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

#include<iostream>
#include<queue>
using namespace std;
typedef long long LL;
//first升序排序，若first相等，second升序排序，存储{权值，下标}；
typedef pair<LL,int> PII;
const int N=5e5+10;
LL l[N],r[N],v[N];
//删除x节点
void del(int x){v[l[x]]+=v[x];v[r[x]]+=v[x];r[l[x]]=r[x];l[r[x]]=l[x];
}
int main(){int n,k;cin>>n>>k;//小根堆；priority_queue<PII,vector<PII>,greater<PII>> h;for(int i=1;i<=n;i++){cin>>v[i];l[i]=i-1;r[i]=i+1;h.push({v[i],i});}//构造双向链表r[0]=1;l[n+1]=n;while(k--){auto t=h.top();h.pop();//若当前点值改变，则该点值增大，不会是最小值，需要重新放回堆中if(t.first!=v[t.second]){k++;h.push({v[t.second],t.second});}else{del(t.second);}}int t=r[0];while(t!=n+1){cout<<v[t]<<' ';t=r[t];}return 0;
}

 

这篇关于【小根堆+双链表】蓝桥杯第十四届--整数删除的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---