手写堆求助
查看原帖
手写堆求助
733659
鶴守丶葉七楼主2024/5/28 22:58

照着深进上改的小根堆,样例输出16(1+1+1+2+2+9),不明白哪里错了

#include<bits/stdc++.h>
using namespace std;
long long n,s,res;
long long w[10005];
long long tot;
long long top(){
    return w[1];
}
void modify(int x){
    if(x==1|w[x]<w[x/2]){
        return;
    }
    else{
        swap(w[x],w[x/2]);
        modify(x/2);
    }
}
void push(int x){
    w[++tot]=x;
    modify(tot);
}
void repair(int x){
    if(x*2>tot)return;
    int tar=x*2;
    if(x*2+1>=tot){
        tar=w[x*2]<w[x*2+1]?x*2:x*2+1;
    }
    if(w[x]<w[tar]){
        swap(w[x],w[tar]);
        repair(tar);
    }
}
void pop(){
    swap(w[1],w[tot--]);
    repair(1);
}
int main(){
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>s;
        push(s);
    }
    for(int i=1;i<=n;i++){
        s=0;
        s+=top();
        pop();
        s+=top();
        res+=s;
    }
    cout<<res<<endl;
    return 0;
}
2024/5/28 22:58
加载中...