题目链接
#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;
}