讨论 / 堆排序能不能解此题?
L.Lawliet 2010-10-04 01:31:00
点我顶贴 收藏 删除
[color=red]第一个点显示的错误信息正确答案居然无输出?![/color]

哪位大牛说说自己想法

我写了100行的堆排序 wa0分...

const maxn=100000000;

var a{max},b{min}:array[0..maxn]of longint;

i,j,k,m,n,total:longint;

sum:qword;

procedure maxdown(i:longint);

var j,t,r:longint;

begin

while true do

begin

j:=i*2;

if j>total then exit;

if (j<total)and(a[j+1]>a[j]) then inc(j);

if a[i]<a[j] then

begin

t:=a[i];

a[i]:=a[j];

a[j]:=t;

i:=j;

end

else exit;

end;

end;

procedure maxup(i:longint);

var j,t,r:longint;

begin

while true do

begin

j:=i div 2;

if j=0 then exit;

if a[j]<a[i] then

begin

t:=a[i];

a[i]:=a[j];

a[j]:=t;

{necessary?} maxdown(j);

i:=j;

end

else exit;

end;

end;

procedure mindown(i:longint);

var j,t,r:longint;

begin

while true do

begin

j:=i*2;

if j>total then exit;

if (j<total)and(b[j+1]<b[j]) then inc(j);

if b[i]>b[j] then

begin

t:=b[i];

b[i]:=b[j];

b[j]:=t;

i:=j;

end

else exit;

end;

end;

procedure minup(i:longint);

var j,t,r:longint;

begin

while true do

begin

j:=i div 2;

if j=0 then exit;

if b[j]>b[i] then

begin

t:=b[i];

b[i]:=b[j];

b[j]:=t;

{necessary?} mindown(j);

i:=j;

end

else exit;

end;

end;

{main}

begin

readln(n); sum:=0; total:=0;

for n:=1 to n do

begin

read(k);

for i:=1 to k do

begin

read(m);

inc(total);

a[total]:=m;

b[total]:=m;

maxup(total);

minup(total);

end;

sum:=sum+a[1]-b[1];

a[1]:=a[total];

b[1]:=b[total];

dec(total);

maxdown(1);mindown(1);

end;

writeln(sum);

end.

查看更多回复
提交回复