根本就不用排序，其实就是个贪心。
每次找最小的两堆合并就可以啦。

{真不懂某些人只发个代码出来干什么？又没人看，浪费空间}

#include<cstdio>
#include<queue>
using namespace std;
#define IOFileName "P1097"
int n,ai,x,y,ans=0;
priority_queue<int,deque<int>,greater<int> >a;
int main(){
freopen(IOFileName".in","r",stdin);
freopen(IOFileName".out","w",stdout);
scanf("%d\n",&n);
for(int i=0;i<n;i++){
scanf("%d ",&ai);
a.push(ai);
}
while(a.size()>1){
x=a.top();a.pop();
y=a.top();a.pop();
a.push(x+y);
ans+=x+y;
}
printf("%d\n",ans);
}
90MS+276KB

#include<iostream>
#include<iomanip>
#include<string>
#include<algorithm>
#include<ctime>
using namespace std;

int a[10010];
void qsort(int l,int r)
{
int i,j,mid,p;
i=l;
j=r;
mid=a[(l+r)/2];
while(i<=j)
{
while(a[i]<mid) i++;
while(a[j]>mid) j--;
if(i<=j)
{
p=a[i];
a[i]=a[j];
a[j]=p;
i++;
j--;

}

}
if(l<j) qsort(l,j);
if(i<r) qsort(i,r);
}
int main()
{
int n,e=0,y=0;
cin>>n;
for(int i=1;i<=n;i++)
cin>>a[i];

qsort(1,n);
for(int i=2;i<=n;i++)
{
a[i]=a[i]+a[i-1];
e=e+a[i];

int q=a[i];
for(int j=i;j<=n;j++)
{
if(a[j]<=a[i]&&a[j+1]>=a[i]||a[j]<a[i]&&j==n)
{
y=1;
for(int o=i;o<=j-1;o++)
{
a[o]=a[o+1];

}
a[j]=q;
}

if(y==1) break;

}

y=0;
}
cout<<e;

return 0;

}

#include<iostream>
using namespace std;

int heap[20010];
void heapdown(int i,int n)
{
int j;
j=i*2;
while(j<=n)
{
if(j<n&&heap[j+1]<heap[j]) j++;
if(heap[i]<=heap[j]) break;
swap(heap[i],heap[j]);
i=j;
j=i*2;
}
}
int main()
{
int n,k,l,ans=0;
cin>>n;
for(int i=1;i<=n;i++)
cin>>heap[i];
for(int i=n;i>=1;i--)
heapdown(i,n);
for(int i=1;i<n;)
{
k=heap[1]+heap[2];
l=heap[1]+heap[3];
if(k<l)
{

heap[2]=k;
ans=ans+k;
heap[1]=heap[n];
n--;
heapdown(2,n);
heapdown(1,n);
}

else
{
heap[3]=l;
ans=ans+l;
heap[1]=heap[n];
n--;
heapdown(3,n);
heapdown(1,n);
}

}
cout<<ans<<endl;

return 0;

}

int main()
{
int x,N,goup[10000],i,n,j,t,sum=0;
scanf("%d",&N);
for(i=0;i<N;i++)
scanf("%d",&goup[i]);
for(i=0;i<N-1;i++)
{ n=i;
for(j=i+1;j<N;j++)
{if(goup[n] > goup[j]) n=j;}
t=goup[i];goup[i]=goup[n];goup[n]=t;}
for(i=0;i<N-1;i++)
{goup[i+1]=goup[i]+goup[i+1];
sum=sum+goup[i+1];
for(x=i+1;x<i+3;x++)
{n=x;
for(j=x+1;j<N;j++)
{if(goup[n]>goup[j])n=j;}
t=goup[x];goup[x]=goup[n];goup[n]=t;} }
if(N>2)printf("%d",sum);
if(N==1)printf("%d",goup[0]);
if(N==2)printf("%d",goup[0]+goup[1]);
}

优于快排的算法

#include<stdio.h>
int main()
{
int x,N,goup[10000],i,n,j,t,sum=0;
scanf("%d",&N);
for(i=0;i<N;i++)
scanf("%d",&goup[i]);

for(i=0;i<N-1;i++)
{
n=i;
for(j=i+1;j<N;j++)
{if(goup[n] > goup[j]) n=j;}
t=goup[i];goup[i]=goup[n];goup[n]=t;}

for(i=0;i<N-1;i++)
{goup[i+1]=goup[i]+goup[i+1];
sum=sum+goup[i+1];
for(x=i+1;x<i+3;x++)
{n=x;
for(j=x+1;j<N;j++)
{if(goup[n]>goup[j])n=j;}
t=goup[x];goup[x]=goup[n];goup[n]=t;}
}
if(N>2)printf("%d",sum);
if(N==1)printf("%d",goup[0]);
if(N==2)printf("%d",goup[0]+goup[1]);
}

优于快排的算法

program fruit;
var i:longint;
mindui:array[0..100100] of int64;
frut,duia,duib,size,s,n:int64;
procedure huan(var a,b:int64);
var m:int64;
begin
m:=a;
a:=b;
b:=m;
end;
procedure up(var a:int64);
var fa:int64;
begin
if a=1 then exit;
fa:=a div 2;
if mindui[fa]<=mindui[a] then exit;
huan(mindui[fa],mindui[a]);
up(fa);
end;
procedure down( a:int64);
var son:int64;
begin
son:=2*a;
if son>size then exit;
if (son+1<=size)and(mindui[son]>mindui[son+1])
then inc(son);
if mindui[son]>=mindui[a]
then exit;
huan(mindui[son],mindui[a]);
down(son);
end;
begin
readln(n);size:=0;s:=0;
for i:=1 to n do
begin
read(frut);
inc(size);
mindui[size]:=frut;
up(size);
end;
for i:=1 to n-1 do
begin
duia:=mindui[1];
mindui[1]:=mindui[size];
dec(size);
down(1);
duib:=mindui[1];
mindui[1]:=mindui[size];
dec(size);
down(1);
s:=s+duia+duib;
inc(size);
mindui[size]:=duia+duib;
up(size);
end;
writeln(s);
end.

帮我看看哪里错了

测试数据 #0: TimeLimitExceeded, time = 1015 ms, mem = 1132 KiB, score = 0

测试数据 #1: Accepted, time = 0 ms, mem = 1132 KiB, score = 10

测试数据 #2: WrongAnswer, time = 15 ms, mem = 1132 KiB, score = 0

测试数据 #3: WrongAnswer, time = 31 ms, mem = 1128 KiB, score = 0

测试数据 #4: WrongAnswer, time = 343 ms, mem = 1132 KiB, score = 0

测试数据 #5: WrongAnswer, time = 671 ms, mem = 1132 KiB, score = 0

测试数据 #6: TimeLimitExceeded, time = 1015 ms, mem = 1136 KiB, score = 0

测试数据 #7: TimeLimitExceeded, time = 1015 ms, mem = 1132 KiB, score = 0

测试数据 #8: TimeLimitExceeded, time = 1015 ms, mem = 1128 KiB, score = 0

测试数据 #9: TimeLimitExceeded, time = 1015 ms, mem = 1132 KiB, score = 0
var b,i,j,m,n:integer;
a:array[0..200000]of integer;
procedure sort(l,r: longint);
var i,j,x,y: longint;
begin
i:=l;
j:=r;
x:=a[(l+r) div 2];
repeat
while a[i]>x do
inc(i);
while x>a[j] do
dec(j);
if not(i>j) then
begin
y:=a[i];
a[i]:=a[j];
a[j]:=y;
inc(i);
j:=j-1;
end;
until i>j;
if l<j then
sort(l,j);
if i<r then
sort(i,r);
end;
begin
read(n);
for i:=1 to n do
read(a[i]);
m:=n;
for j:=1 to m-1 do
begin
sort(1,n);
a[n-1]:=a[n-1]+a[n];
b:=b+a[n-1];
n:=n-1;
end;
writeln(b);
end.

Vijos 题解：http://hi.baidu.com/umule/item/2c997f8ed9600fdae596e017
有疑问请留言 共同进步

这题队列的数组记得要使用Longint，否则就会30分。

最简单的方法是使用优先队列，那个会自动管理当前优先级最高的元素

最小的最早合并

//stl碉堡了。。。。

#include<cstdio>
#include<cstring>
#include<queue>

int main(){
int n,tmp,ans=0;
std::priority_queue<int> q;
scanf("%d\n",&n);
for (int i=1;i<=n;i++){
scanf("%d",&tmp);
q.push(-tmp);
}
for (int i=1;i<n;i++){
tmp=q.top();q.pop();
tmp+=q.top();q.pop();
q.push(tmp);
ans-=tmp;
}
printf("%d\n",ans);
return 0;
}

var
a:array[0..10000]of longint;
m,n,x,ans,i:longint;
procedure down(i:longint);
var
x,j:longint;
begin
while i*2<=n do
begin
j:=i*2;
if 2*i+1<=n then if a[j]>a[j+1] then j:=j+1;
if a[j]<a[i] then
begin
x:=a[j];
a[j]:=a[i];
a[i]:=x;
end else break;
i:=j;
end;
end;
begin
//assign(input,'a1.in'); reset(input);
readln(n);
for i:=1 to n do read(a[i]);
for i:=n div 2 downto 1 do down(i);
m:=n;
ans:=0;
for i:=1 to m-1 do
begin
x:=a[1];
a[1]:=a[n];
dec(n);
down(1);
inc(ans,x+a[1]);
a[1]:=a[1]+x;
down(1);
end;
writeln(ans);
end.
为什么楼下的堆排们代码如此长？

测试数据 #0: Accepted, time = 0 ms, mem = 852 KiB, score = 10
测试数据 #1: Accepted, time = 0 ms, mem = 848 KiB, score = 10
测试数据 #2: Accepted, time = 0 ms, mem = 848 KiB, score = 10
测试数据 #3: Accepted, time = 0 ms, mem = 852 KiB, score = 10
测试数据 #4: Accepted, time = 0 ms, mem = 848 KiB, score = 10
测试数据 #5: Accepted, time = 0 ms, mem = 848 KiB, score = 10
测试数据 #6: Accepted, time = 0 ms, mem = 848 KiB, score = 10
测试数据 #7: Accepted, time = 0 ms, mem = 848 KiB, score = 10
测试数据 #8: Accepted, time = 0 ms, mem = 848 KiB, score = 10
测试数据 #9: Accepted, time = 0 ms, mem = 848 KiB, score = 10
Accepted, time = 0 ms, mem = 852 KiB, score = 100
运用堆排序，0ms秒过

program fruit;
var
heap : array[1..30000] of longint;
ans,n,i,tmp,a,b,len : longint;
procedure put(x:longint);
var
fa,son,tmp : longint;
begin
len := len + 1;
heap[len] := x;
son := len;
while (son <> 1) and (heap[son div 2]>heap[son]) do
begin
tmp := heap[son div 2];
heap[son div 2] := heap[son];
heap[son] := tmp;
son := son div 2;
end;
end;
function get : longint;
var
fa,son,tmp : longint;
stop : boolean;
begin
get := heap[1];
heap[1] := heap[len];
dec(len);
fa := 1;
stop := false;
while ((fa * 2 <= len) or (fa * 2 + 1 <= len)) and (not stop) do
begin
if (fa * 2 + 1 > len) or (heap[fa * 2]<heap[fa * 2+1]) then son := fa * 2 else son := fa * 2 + 1;
if heap[fa] > heap[son] then begin
tmp := heap[fa];
heap[fa] := heap[son];
heap[son] := tmp;
fa := son;
end else stop := true;
end;
end;
begin
//assign(input,'fruit.in');
//assign(output,'fruit.out');
reset(input);
rewrite(output);
len := 0;
readln(n);
for i := 1 to n do
begin
read(tmp);put(tmp);
end;
ans := 0;
for i := 1 to n - 1 do
begin
a := get;b := get;
ans := ans + a + b;
put(a+b);
end;
writeln(ans);
// close(input);
//close(output);
end.

贪心

最小的最早合并

证明

1. 第i次合并的果子从头至尾共消耗的力气是*(n-i+1)*weight* (weight是该堆果子的重量)
2. 所以合并n堆的果子的序列如果是(b1,b2,b3,b4……,bn),则总消耗体力 n*weight[b1]+(n-1)*weight[b2]+(n-2)*weight[b3]+...+1*weight[bn]
3. 由此，大家可以很容易的看出重量最小的应当最先合并。
4. 只需先从小到大排序，然后大家应该清楚该怎么做了。 代码我就留给大家自行完成了。

#include<iostream>
using namespace std;

long long a[10001],f[10001][10001],b[10001],r,c;

void jd(int x,int y)
{
int i=x;

while(i*2<=y)
{
int k=2*i;

if (k+1<=y)
if (a[k]>a[k+1]) k++;

if (a[k]<a[i])
{
swap(a[k],a[i]);
i=k;
}

else return;

}

}

int main()
{
int i,j,n,k,t,a1,a2;
cin>>n;

for(i=1;i<=n;i++)
cin>>a[i];

for(i=n/2;i>=1;i--) jd(i,n);

int d=0;

for(int i=1;i<=n-1;i++)
{
a1=a[1];
a[1]=a[n-i+1];
jd(1,n-i);

a2=a[1];
t=a1+a2;
d=d+t;
a[1]=t;
jd(1,n-i);

}

cout<<d;

return 0;
}

堆排秒杀

o(￣▽￣)o 水过~~~~
Var n,i,j,total,ans,tmp1,tmp2,y:longint;
a:array[1..50000] of longint;
Procedure down(i:longint);
Var j,y:longint;
Begin
While i*2<=total Do
Begin
j:=i*2;
If (a[j]>a[j+1]) and (j<total) then inc(j);
If a[j]<a[i] then
Begin
y:=a[i];
a[i]:=a[j];
a[j]:=y;
i:=j;
End
Else break;
End;
End;
Begin
assign(input,'input.txt');
reset(input);
Readln(n);
total:=n;
For i:=1 to n do read(a[i]);
For i:=n div 2 downto 1 do down(i);
While total<>1 do
Begin
tmp1:=a[1];
y:=a[1];
a[1]:=a[total];
a[total]:=y;
dec(total);
down(1);
tmp2:=a[1];
a[1]:=tmp2+tmp1;
ans:=ans+tmp1+tmp2;
down(1);
End;
writeln(ans);
readln;
End.

=皿= 为毛好好的代码都要左对齐！

快排