【问题描述】
在一个果园里，多多已经将所有的果子打了下来，而且按果子的不同种类分成了不同的堆。多多决定把所有的果子合成一堆。
每一次合并，多多可以把两堆果子合并到一起，消耗的体力等于两堆果子的重量之和。可以看出，所有的果子经过n-1次合并之后，就只剩下一堆了。多多在合并果子时总共消耗的体力等于每次合并所耗体力之和。
因为还要花大力气把这些果子搬回家，所以多多在合并果子时要尽可能地节省体力。假定每个果子重量都为1，并且已知果子的种类数和每种果子的数目，你的任务是设计出合并的次序方案，使多多耗费的体力最少，并输出这个最小的体力耗费值。
例如有3种果子，数目依次为1，2，9。可以先将1、2堆合并，新堆数目为3，耗费体力为3。接着，将新堆与原先的第三堆合并，又得到新的堆，数目为12，耗费体力为12。所以多多总共耗费体力=3+12=15。可以证明15为最小的体力耗费值。
【样例输入】
3
1 2 9
【样例输出】
15
【解题思路】
本题为NOIP2004提高组第二题，有两种方法可以解答。一个是贪心+堆，另一个是双排序队列。
先来说说贪心+堆。
首先，建一个小根堆，这样就保证根为最小的，取出根并维护小根堆，再取出根并维护小根堆，这样就得到了我们需要的结果，把结果插入堆中并维护，反复这个操作n-1次即可。详见代码。
然后是队列。
首先将果子排序，构成一个序列，将最前面的两堆果子取出，放入另一个队列，接下来，就只要判断之后应该取哪两堆，要么取最先的队列中的前两个，要么取新的队列中的前两个，要么取两个队列最前面的一个，然后再放到新的队列中，这样就能保证新的队列必是一个排序好的队列。将新的队列中的每个数加起来便是结果。
【代码实现】
var a:array[..] of longint;
i,n,k,ans,n1:longint;
procedure swap(var a,b:longint);
var y:longint;
begin
y:=a;a:=b;b:=y;
end;
procedure sift(i,m:longint);
var k:longint;
begin
a[]:=a[i];
k:=*i;
while k<=m do
begin
if (k<m)and(a[k]<a[k+]) then
inc(k);
if a[]<a[k] then
begin
a[i]:=a[k];
i:=k;
k:=i*;
end
else
k:=m+;
end;
a[i]:=a[];
end;
procedure heapsort;
var j:longint;
begin
for j:=n div downto do
sift(j,n);
for j:=n downto do
begin
swap(a[],a[j]);
sift(,j-);
end;
end;
function deletemin:longint;
var i,pos:longint;
begin
i:=;
deletemin:=a[];
a[]:=a[n1];
dec(n1);
while *i<=n1 do
begin
pos:=*i;
if (pos<n1)and(a[pos+]<a[pos]) then
inc(pos);
if a[i]>a[pos] then
begin
swap(a[i],a[pos]);
i:=pos;
end
else
break;
end;
end;
procedure insert(k:longint);
var i:longint;
begin
inc(n1);
a[n1]:=k;
i:=n1;
while (i div >)and(a[i div ]>k) do
begin
swap(a[i],a[i div ]);
i:=i div ;
end;
end;
begin
readln(n);
for i:= to n do
read(a[i]);
heapsort;
n1:=n;
for i:= to n- do
begin
k:=deletemin;
k:=k+deletemin;//取出根并维护
ans:=ans+k;
insert(k);//插入结果并维护
end;
writeln(ans);
end.
var old,new:array[..] of longint;
i,n,fo,fn,rn,ans:longint;
procedure swap(var i,j:longint);
var y:longint;
begin
y:=i;i:=j;j:=y;
end;
procedure sift(i,m:longint);
var k:longint;
begin
old[]:=old[i];
k:=*i;
while k<=m do
begin
if (k<m)and(old[k]<old[k+]) then
inc(k);
if old[]<old[k] then
begin
old[i]:=old[k];
i:=k;
k:=*i;
end
else
k:=m+;
end;
old[i]:=old[];
end;
procedure heapsort;
var j:longint;
begin
for j:=n div downto do
sift(j,n);
for j:=n downto do
begin
swap(old[],old[j]);
sift(,j-);
end;
end;
begin
readln(n);
for i:= to n do
read(old[i]);
heapsort;//这个排序可以是堆排，二叉排序树，快排等等，因为我今天复习到堆，就用堆排了
fo:=;
new[]:=old[]+old[];
ans:=new[];
fn:=;
rn:=;
repeat
if (old[fo+]<>)and(old[fo+]<new[fn])then
begin
inc(rn);
new[rn]:=old[fo]+old[fo+];
ans:=ans+new[rn];
inc(fo,);
end
else
if (new[fn+]<>)and(new[fn+]<old[fo]) then
begin
inc(rn);
new[rn]:=new[fn]+new[fn+];
ans:=ans+new[rn];
inc(fn,);
end
else
if (old[fo]=)and(new[fn+]<>) then
begin
inc(rn);
new[rn]:=new[fn]+new[fn+];
ans:=ans+new[rn];
inc(fn,);
end
else
begin
inc(rn);
new[rn]:=new[fn]+old[fo];
ans:=ans+new[rn];
inc(fo);
inc(fn);
end;
until (old[fo+]=)and(new[fn+]=);
writeln(ans);
end.