这是我的代码,大佬们帮忙看看down函数就行。没有注释掉的down函数不能AC,加注释的可以AC,帮帮蒟蒻吧。
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
int size;//记录当前堆中的元素个数
void swap(int *a,int *b){
int temp=*a;
*a = *b,*b=temp;
}
void up(int now,int *heapmin)
{
while(now>1){
if(heapmin[now]<heapmin[now/2]){
swap(&heapmin[now],&heapmin[now/2]);
now/=2;
}
else{
break;
}
}
}
void insert(int val,int *heapmin)
{
heapmin[++size]=val;
up(size,heapmin);//由底向顶调整
}
void down(int *heapmin){
int tmp=1;
while(tmp<=(size/2)){
if(heapmin[tmp<<1]>heapmin[tmp<<1|1]&&(tmp*2+1<=size)){
swap(&heapmin[tmp<<1],&heapmin[tmp<<1|1]);
}
if(heapmin[tmp]>heapmin[tmp<<1]){
swap(&heapmin[tmp],&heapmin[tmp<<1]);
tmp=tmp<<1;
}
else{
break;
}
}
}/*
void down(int p,int *heap) //二叉小根堆向下调整
{
int s=p*2;
while(s<=size)
{ //下面这句话是从左右儿子中选一个更小的做交换
if(s<size&&heap[s+1]<heap[s]) s++;
if(heap[s]<heap[p])
{
swap(&heap[s],&heap[p]);
p=s; s=p*2;
}
else break;
}
}*/
void extract(int *heapmin)//小顶堆删除堆顶
{
heapmin[1]=heapmin[size--];
down(heapmin);
}
int main()
{
int n,i,ans=0;
scanf("%d",&n);
int heapmin[100009];//小根堆
for(i=1;i<=n;i++)
{
int tmp;
scanf("%d",&tmp);
insert(tmp,heapmin);
}
for(i=1;i<n;i++)
{
int x=heapmin[1];
extract(heapmin);
int y=heapmin[1];
extract(heapmin);
ans+=x+y;
insert(x+y,heapmin);
}
printf("%d",ans);
return 0;
}