讨论 - 走过路过的神牛帮忙看看那里错了，只求结果对

waiting~ 2012-03-07 07:27:00

点我顶贴收藏删除

program fruit;

var

min:qword;

n,tt,t,temp,tmp:longint;

a:array[1..10000]of longint;

procedure init;

var

i,j:longint;

begin

readln(n);

for i:=1 to n do

read(a[i]);

end;

procedure find;

var

i:longint;

begin

temp:=maxint;

tmp:=maxint;

for i:=1 to n do

if (a[i]<>0) and (a[i]<=temp) then begin temp:=a[i]; t:=i; end;

for i:=1 to n do

if (a[i]>=temp) and (a[i]<=tmp) and (i<>t) and (a[i]<>0) then begin tmp:=a[i]; tt:=i; end;

end;

procedure work;

var

i,j:longint;

begin

i:=0;

repeat

inc(i);

min:=min+temp+tmp;

a[tt]:=temp+tmp;

a[t]:=0;

find;

until i=n-1;

end;

begin

min:=0;

init;

find;

work;

writeln(min);

end.

#1 waiting~@2012-02-03 16:48:00

回复删除

重新粘贴一次，上面有东西没改，提交错了

状态: Unaccepted

测评机： Xeond[6]

得分： 50分

提交日期： 2012-2-4 8:38:00

有效耗时： 1266毫秒

测试结果1: 通过本测试点|有效耗时172ms

测试结果2: 通过本测试点|有效耗时172ms

测试结果3: 通过本测试点|有效耗时172ms

测试结果4: 通过本测试点|有效耗时328ms

测试结果5: 通过本测试点|有效耗时422ms

测试结果6: 选手程序运行超过时限

测试结果7: 测试结果错误.错误结果为:131173003

正确结果应为:199205993

测试结果8: 测试结果错误.错误结果为:131173003

正确结果应为:130108340

测试结果9: 选手程序运行超过时限

测试结果10: 测试结果错误.错误结果为:131173003

正确结果应为:260332759

提交代码： view sourceprint?01.program fruit;

02.

var

03.

min:qword;

04.

n,tt,t,temp,tmp:longint;

05.

a:array[1..10000]of longint;

06.

procedure init;

07.

var

08.

i,j:longint;

09.

begin

10.

readln(n);

11.

for i:=1 to n do

12.

read(a[i]);

13.

end;

14.

procedure find;

15.

var

16.

i:longint;

17.

begin

18.

temp:=maxlongint;

19.

tmp:=maxlongint;

20.

for i:=1 to n do

21.

if (a[i]<>0) and (a[i]<=temp) then begin temp:=a[i]; t:=i; end;

22.

for i:=1 to n do

23.

if (a[i]>=temp) and (a[i]<=tmp) and (i<>t) and (a[i]<>0) then begin tmp:=a[i]; tt:=i; end;

24.

end;

25.

procedure work;

26.

var

27.

i,j:longint;

28.

begin

29.

i:=0;

30.

repeat

31.

inc(i);

32.

min:=min+temp+tmp;

33.

a[tt]:=temp+tmp;

34.

a[t]:=0;

35.

find;

36.

until i=n-1;

37.

end;

38.

begin

39.

min:=0;

40.

init;

41.

find;

42.

work;

43.

writeln(min);

44.

end.

7.8.10在FPC上测得结果是正确结果啊，为甚是这样

#2 zfj19960705@2012-03-07 07:27:00

回复删除

Name: P1097合并果子

Copyright: 始发于goal00001111的专栏；允许自由转载，但必须注明作者和出处

Author: goal00001111

Date: 11-12-08 15:15

题目分析：

本题的指导思想并不难，就是将所有的果子堆数按增序排列，每次将最小的两个堆合并，直到堆数为1为止，这样消耗的体力肯定是最少的。

这和构造赫夫曼树的算法不是一般的相似啊！

我们可以构造一棵赫夫曼树，累计所有非叶子结点的值就得到了最小体力总数。

没有人想超时，所以我们在构造赫夫曼树的时候，寻找两个最小结点的算法是不能用时间复杂度为O(N)的常规方法的，我这里使用了一个二叉堆，这样在寻找最小结点时时间复杂度为O(logN)。

除此之外我们还有一种方法：队列算法。

就是构造两个队列oldQueue 和 newQueue，oldQueue用来存储原有的果子堆数，

newQueue用来存储每次合并得到的新果子堆数，当两个队列都遍历完后，累加newQueue的元素值，就得到了总共耗费的体力值。

要想得到最小的体力耗费值则 oldQueue要按增序排列，很明显每次合并时候是在oldQueue 和 newQueue的首部取两个最小值，合并的值插入到 newQueue尾部。

此种方法的好处是只需对oldQueue进行一次排序，之后就不再需要排序，而是直接在oldQueue 和 newQueue的首部取值就好了。

由于oldQueue的元素是从a[]中复制过来的，所以我们可以对其进行插入排序，这样排序的时间复杂度是O(N*logN)；但如果我们注意观察的话，可以发现输入数据1<＝ai<=20000，我们完全可以使用基数排序，以空间换时间，使得时间复杂度降低到O(N)。

说明：

算法思想：迭代和递归。

数据结构：数组，队列，结构数组（赫夫曼树），二叉堆。

时间复杂度：赫夫曼编码法O(N/2*logN + logN!)，队列法：插入排序O(N*logN)，基数排序O(N);

空间复杂度：O(MAX);

程序语言：分别用c++和pascal实现。

附注：分别提供了赫夫曼编码法和队列法实现代码。

关于赫夫曼编码的详细内容请参考拙作《赫夫曼编码》：

http://blog.csdn.net/goal00001111/archive/2008/12/16/3533984.aspx

#3 zfj19960705@2012-03-07 07:27:00

回复删除

PROGRAM P1097 (input, output);

TYPE

HuffmanTree = record

weight : longword;

lc, rc : integer;

end;

CONST

MAX = 10000;

VAR

hT : array [1..MAX*2] of HuffmanTree;

w : array [1..MAX] of longword;

i,n : integer;

sum : longword;

PROCEDURE BuildHeap(len : integer); FORWARD;

PROCEDURE PercDown(pos, len : integer); FORWARD;

PROCEDURE DeleteMin(len : integer); FORWARD;

PROCEDURE InsertHfHuffmanTree(len : integer; x : HuffmanTree); FORWARD;

{创建一棵赫夫曼树}

PROCEDURE CreateHuffmanTree(n : integer);

var

i, left, right : integer;

add : HuffmanTree;

begin

for i:=1 to n do {初始化赫夫曼树}

begin

hT[i].weight := w[i];

hT[i].lc := 0;

hT[i].rc := 0;

end; {for}

BuildHeap(n); {构造一个二叉堆；小顶堆}

left := n;

right := n;

while left > 1 do {此处通过减小和增大left的值来改变二叉堆的大小}

begin

inc(right);

hT[right] := hT[1];

add.weight := hT[1].weight;

add.lc := right; {存储左孩子下标}

DeleteMin(left);

hT[left] := hT[1];

add.weight := add.weight + hT[1].weight;

add.rc := left; {存储右孩子下标}

dec(left);

DeleteMin(left);

InsertHfHuffmanTree(left, add);

end; {while}

end; {CreateHuffmanTree}

{构造一个二叉堆；小顶堆}

PROCEDURE BuildHeap(len : integer);

var

i : integer;

begin

for i:=len div 2 downto 1 do

PercDown(i, len);

end; {BuildHeap}

{构造二叉堆的功能子函数}

PROCEDURE PercDown(pos, len : integer);

var

child : integer;

min : HuffmanTree;

begin

min := hT[pos];

while (pos * 2 ) <= len do

begin

child := pos * 2;

if (child <> len) and (hT[child+1].weight < hT[child].weight) then

inc(child);

if min.weight > hT[child].weight then

begin

hT[pos] := hT[child];

pos := child;

end {if}

else

len := pos; {此语句的目的是为了跳出循环}

end; {while}

hT[pos] := min;

end; {PercDown}

{删除二叉堆的根，并通过上移使得新得到的序列仍为二叉堆}

PROCEDURE DeleteMin(len : integer);

var

child, pos : integer;

last : HuffmanTree;

begin

pos := 1;

last := hT[len];

dec(len);

while (pos * 2) <= len do {把二叉堆的某些元素往前移，使得新得到的序列仍为二叉堆}

begin

child := pos * 2;

if (child <> len) and (hT[child+1].weight < hT[child].weight) then {若i有右儿子，且右儿子小于左儿子，c指向右儿子}

inc(child);

if last.weight > hT[child].weight then {若i的小儿子小于二叉堆的最后一个元素，把其移到i的位置}

begin

hT[pos] := hT[child];

pos := child;

end {if}

else

len := pos; {此语句的目的是为了跳出循环}

end; {while}

hT[pos] := last; {把二叉堆的最后一个元素放到适当的空位，此时得到的序列仍为二叉堆}

end; {DeleteMin}

{把x插入到原长度为len-1的二叉堆}

PROCEDURE InsertHfHuffmanTree(len : integer; x : HuffmanTree);

var

i : integer;

begin

i := len;

while (i div 2 > 0) and (hT[i div 2].weight > x.weight) do

begin

hT[i] := hT[i div 2];

i := i div 2;

end; {while}

hT[i] := x;

end; {BuildHeap}

{先序遍历赫夫曼树，累计非叶子结点的值}

PROCEDURE Preorder(var sum : longword; p : integer);

begin

if hT[p].lc > 0 then

begin

sum := sum + hT[p].weight;

Preorder(sum, hT[p].lc); {遍历左子树}

Preorder(sum, hT[p].rc); {遍历右子树}

end; {if}

end; {Preorder}

BEGIN

read(n);

for i:=1 to n do

read(w[i]);

CreateHuffmanTree(n);

sum := 0;

Preorder(sum, 1); {先序遍历赫夫曼树，累计非叶子结点的值}

writeln(sum);

END.