合并果子

October 12, 2008

这是NOIP2004年提高组的一道题，随便搜索就能找到，VIJOS和RQNOJ都有。

这道题有很多很多种做法，首先最重要的是仔细读题，题中合并可以不按顺序，所以就不是石子归并的DP，直接贪心找最小即可。估计这道题当年坑了很多人。还有刚开始考虑时间复杂度，写得不一定对。。错了请指出来。

方法一，也就是最容易想到的，快排+插入排序。时间复杂度为O(n^2)。

program fruit;
var
    n,i:longint;
    a:array[1..10000] of longint;
    ans,temp,s:longint;
procedure qsort(left,right:longint);
var
    i,j,x,p:longint;
begin
    i:=left;
    j:=right;
    p:=i+random(j-i);
    x:=a[p];
    a[p]:=a[i];
    while i=x) do inc(i);
        a[j]:=a[i];
    end;
    a[i]:=x;
    if i>left then qsort(left,i-1);
    if i1 do
    begin
        a[n-1]:=a[n-1]+a[n];
        dec(n);
        s:=s+a[n];
        i:=n-1; //这个地方很容易错，不减1则无法进入循环。
        temp:=a[n];
        while (i>0) and (temp>a[i]) do
        begin
            a[i+1]:=a[i];
            dec(i);
        end;
        a[i+1]:=temp;
    end;
    writeln(s);
    close(output);
end.

方法二，堆排序，刚学的。时间复杂度为O(nlogn)

program heaptest;
var
    i,n,s,t:longint;
    a:array[1..10000] of longint;
    x,y:longint;
procedure shift(k:longint);
var
    i,x:longint;
begin
    x:=a[k];
    i:=2*k;
    while i<=n do
    begin
        if (i<n) and (a[i]>a[i+1]) then inc(i);
        if a[i]1 do
    begin
        x:=a[1];
        a[1]:=a[n];
        dec(n);
        shift(1);
        y:=a[1];
        s:=s+x+y;
        a[1]:=x+y;
        shift(1);
    end;
    writeln(s);
    close(input);
    close(output);
end.

方法三，构造huffman树，而且可以简略一些，最后循环输出权值即可。但是只能过几组数据，会超时。时间复杂度O(n^2)。

program fruitvhuffman;
type
    node=record
        parent:boolean;
        data:longint;
        end;
var
    a:array[1..19999] of node;
    i,j,k,n,ans:longint;
function min(h:longint):longint;
var
    m,i:longint;
begin
    m:=maxlongint;
    for i:=1 to h do
    if (a[i].parent=false) and (a[i].data<m) then
    begin
        m:=a[i].data;
        min:=i;
    end;
end;
begin
    assign(input,'fruit.in');
    assign(output,'fruit.out');
    reset(input);
    rewrite(output);
    fillchar(a,sizeof(a),0);
    readln(n);
    for i:=1 to n do read(a[i].data);
    readln;
    for k:=n+1 to 2*n-1 do
    begin
        i:=min(k-1);
        a[i].parent:=true;
        j:=min(k-1);
        a[j].parent:=true;
        a[k].data:=a[i].data+a[j].data;
    end;
    for i:=n+1 to 2*n-1 do inc(ans,a[i].data);
    writeln(ans);
    close(input);
    close(output);
end.

方法四，时间复杂度为O(n)。一下说明及程序均来源于Misty Sky (CC by-nc-sa)

其实，这道题目还有一种更简单的做法，考虑到每次合并两个结点以后，得到的新结点大小是递增的，于是可以维护两个队列，一个是原队列A，一个是新加入的队列B。每次就一定是在A或（和）B的首部取数，在B的尾部插入。

另外因为a[i]很小只有20000，所以可以使用基数排序，这样整体的时间复杂度就是O(n)。

var
  a,b,c : array[0..20000] of longint;
  la,ra,lb,rb,n,i,p : longint;
  sum : qword;
function get:longint;
begin
  if la>ra then begin inc(lb); exit(b[lb-1]); end;
  if lb>rb then begin inc(la); exit(a[la-1]); end;
  if a[la] < b[lb] then begin
	inc(la);
	exit(a[la-1]);
  end
  else begin
	inc(lb);
	exit(b[lb-1]);
  end;
end;
begin
  readln(n);
  for i := 1 to n do begin
	read(a[i]);
	inc(c[a[i]]);
  end;
  ra := 0;
  for i := 1 to 20000 do
	while not (c[i] = 0) do begin
	  inc(ra);
	  a[ra] := i;
	  dec(c[i]);
	end;
  la := 1;
  lb := 1; rb := 0;
  for i := 1 to n - 1 do begin
	p := get + get;
	inc(rb);
	b[rb] := p;
	inc(sum,p);
  end;
  writeln(sum);
end.

下面是用CENA的时间对比 ```

名称

排名

总得分

有效用时

array

100

0.16

heap

100

0.23

qsort+insert

100

1.97

randomqsort+insert

100

2.01

huffman

0.98

MS这篇不应该写，没什么意义。。就当是备份程序了。换了个显示程序的插件，美观些。
```

```

08.10.19 修改了一下heapsort的代码