优先队列
加上使用数组来模拟链表的pre和next
思路提供
https://www.acwing.com/solution/content/186885/
!!注意数组啥的都要开long long
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
int main(){
int n,k;cin>>n>>k;
priority_queue<pair<ll,int>,vector<pair<ll,int>>,greater<pair<ll,int>>>q;
// 为了防止pre,next越界,所以
// int record[n+2];
// int pre[n+2];int next[n+2];
// pre[0] = 1, next[n + 1] = n;
// // 这样子root的pre回到自己
// // 末尾的next还是自己
// for(int i=1;i<=n;i++)cin>>x,record[i]=x,pre[i]=i-1,next[i]=i+1;
// 当然你不喜欢1-n
ll record[n],pre[n],next[n];
for(int i=0;i<n;i++)
cin>>record[i],pre[i]=i-1,next[i]=i+1,q.push({record[i],i});
while (k--)
{
pair<ll,int>p=q.top();
q.pop();
if(p.first!=record[p.second]){
// 因为删除之后的更新,不能直接在优先队列里面
// 只能更新record
// 主要是因为要相邻!!!!
// 所以用外面的,数值不一样在pop,push
q.push({record[p.second],p.second});
k++;
}
else{
int index=p.second;
if(pre[index]!=-1){//前面可用
record[pre[index]]+=record[index];
next[pre[index]]=next[index];
}
if(next[index]!=n){//后面可用
record[next[index]]+=record[index];
pre[next[index]]=pre[index];
}
}
}
int index;
for(int i=0;i<n;i++)if(pre[i]==-1)index=i;
// 最后一个的pre是-1的,那么他就是root了
while (index!=n)
{
cout<<record[index]<<" ";
index=next[index];
}
}