讨论 / c++AC代码(堆排序)
2019ABC 2019-08-21 21:32:40
点我顶贴 收藏 删除
#include<bits/stdc++.h>

using namespace std;

int heap[20005];

int n,len;

void put(int x){

int now,next;

heap[++len]=x;

now=len;

while(now>1){

next=now>>1;

if(heap[next]>heap[now])swap(heap[next],heap[now]);

now=next;

}

}

int get(){

int res=heap[1],now,next;

heap[1]=heap[len--];

now=1;

while(now*2<=len){

next=now<<1;

if(now*2<n&&heap[next+1]<heap[next])next++;

if(heap[now]<=heap[next])return res;

swap(heap[next],heap[now]);

now=next;

}

return res;

}

int main(){

int x,y,score=0;

scanf("%d",&n);

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

scanf("%d",&x);

put(x);

}

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

x=get();

y=get();

score+=x+y;

put(x+y);

}

printf("%d",score);

return 0;

}

#1 2019ABC@2019-08-21 21:35:20
回复 删除
应该是堆操作,不算堆排序
#2 bfw@2019-08-22 17:08:40
回复 删除
其实这道题目用优先队列写代码比你这个简洁易懂多了……

#3 bfw@2019-08-22 17:09:07
回复 删除
而且这题可以写1e6的,数据太弱。
查看更多回复
提交回复