3155: 蓝桥杯2023年第十四届省赛真题-整数删除

解题思路:

暴力能过5个点，25分。（vector数组实现删数，for循环寻找最小数，每删除一次循环一次）

最小堆，有stl库优先队列priority_queue，堆排序啥的不用咱写了，直接push往里放数就行，存的时存两个值，这个数和这个数的下标，用pair存

注意事项:

存的数组e[ ]开long long

删数加数更新后的数要继续存入堆里

参考代码:

#include <bits/stdc++.h>

using namespace std;

const int N=1e5;

typedef  long long ll;

int e[N],l[N],r[N],idx;

int n,k;

void init(){

r[0]=1,l[1]=0;

idx=2;

}

void insert(int a,int x){

e[idx]=x;

l[idx]=a,r[idx]=r[a];

l[r[a]]=idx,r[a]=idx++;

}

void del(int x){

l[r[x]]=l[x];

r[l[x]]=r[x];

e[l[x]]+=e[x],e[r[x]]+=e[x];

}

int main(){

cin>>n>>k;

init();

priority_queue<pair<ll, int>, vector<pair<ll, int>>, greater<pair<ll, int>>> h;

for(int i=1;i<=n;i++){

int x;

cin>>x;

insert(l[1],x);

h.push({x,i+1});

}

while(k--){

auto p=h.top();h.pop();

if(p.first!=e[p.second]) h.push({e[p.second],p.second}),k++;

else del(p.second);

}

int tt=0;

while(r[tt]!=1){

tt=r[tt];

cout<<e[tt]<<" ";

}

return 0;

}