文章

priority_queue template(优先队列模板)

template

#include<bits/stdc++.h>
using namespace std;
const long long int maxn=5e5+10;
long long int n,k;
long long int flag[maxn];
long long int pre[maxn];
long long int nex[maxn],cnt[maxn],nn[maxn];
////////////////////////////////////////////////////
//pirority_queue template
struct node{
	long long int num,val;
}a;
struct cmp{
	bool operator ()(const node&x,const node &y) const 
	{
		if(x.val!=y.val) return x.val>y.val;
		return x.num>y.num;
	}
};
priority_queue<node,vector<node>,cmp>pr;
////////////////////////////////////////////////////
int main()
{
	long long int i,val,v,l,r,idx;
	cin>>n>>k;
	for(i=1;i<=n;i++){
		pre[i]=i-1;
		nex[i]=i+1;
		cin>>val;
		a.val=val;
		a.num=i;
		pr.push(a);
	}
	while(pr.size()!=n-k){
		a=pr.top();
		pr.pop();
		idx=a.num;
		v=a.val;
		if(cnt[idx]==0){//who need to be removed
			l=pre[idx];
			r=nex[idx];
			nex[l]=r;
			pre[r]=l;
			cnt[l]+=v;
			cnt[r]+=v;
			flag[idx]=1;
		}else {//don't need to be removed
			a.val+=cnt[idx];
			cnt[idx]=0;
			pr.push(a);
		}
	}
	while(pr.empty()!=1){
		a=pr.top();
		pr.pop();
		idx=a.num;
		v=a.val;
		nn[idx]=v+cnt[idx];
	}
	for(i=1;i<=n;i++){
		if(nn[i]!=0){
			cout<<nn[i]<<" ";
		}
	}
	cout<<endl;
	return 0;
}

License:  CC BY 4.0