75. 整数删除

#include<bits/stdc++.h>
using namespace std;
const int N=5e5+10;
int n,k;
priority_queue<pair<long long,int>,vector<pair<long long,int>>,greater<pair<long long,int>>>q;
int pre[N],ne[N];
long long cnt[N],a[N],t;
int main(){
	scanf("%d%d",&n,&k);
	for(int i=1;i<=n;i++){
		scanf("%lld",&t);
		q.push({t,i});
		pre[i]=i-1;
		ne[i]=i+1;
	}
	while(q.size()>n-k){
		long long x=q.top().first; //当前的值
		int id=q.top().second; //当前的下标
		q.pop();
		if(cnt[id]){		
			q.push({x+cnt[id],id});
			cnt[id]=0; //这步很细节，保证了后面的元素被删除之后又可以加到这里
		}
		else{
			int left=pre[id],right=ne[id];
			cnt[left]+=x;
			cnt[right]+=x;
			ne[left]=right; //保证了左边右边隔断
			pre[right]=left;
		}
	}
	while(q.size()){
		long long x=q.top().first;
		int id=q.top().second; //表示剩下数字对应的下标
		q.pop();
		a[id]=x+cnt[id]; //加上它本应该要加上的内容
	}
	for(int i=1;i<=n;i++){
		if(a[i]) cout<<a[i]<<" ";
	}
	return 0;
}