讨论 / 很奇怪
3144046cjc 2008-11-12 16:20:00
点我顶贴 收藏 删除
我不用二叉堆,而是用辅助数组做的,理论复杂度比标程略优,但是却wa在第四个点上,我很奇怪:难道有什么特殊情况我没有考虑?

测试结果错误.错误结果为:28684

正确结果应为:71890

貌似我的结果比标准还优,是不是标程错了?

附:const maxn=100000+1000;

maxm=11;

var tmp,p:array[1..maxm shl 2] of longint;

h,v:array[1..maxn] of longint;

bv,bh,n,m,k,i,j,ans:longint;

procedure sort(l,r:longint);

var i,j,mid,tmp:longint;

begin

if l=r then exit;

i:=l;

j:=r;

mid:=v[(l+r) shr 1];

repeat

while v[i]<mid do inc(i);

while v[j]>mid do dec(j);

if i<=j then

begin

tmp:=v[i];

v[i]:=v[j];

v[j]:=tmp;

inc(i);

dec(j);

end;

until i>j;

if i<r then sort(i,r);

if j>l then sort(l,j);

end;

function calc:int64;

var i,be,en,len,k,x:longint;

sum:array[0..2*maxm] of longint;

min:array[1..maxm*2,1..maxm*2] of longint;

begin

if m=1 then exit(tmp[1]);

for i:=1 to m do tmp[i+m]:=tmp[i];

fillchar(sum,sizeof(sum),0);

for i:=1 to 2*m do sum[i]:=sum[i-1]+tmp[i];

fillchar(min,sizeof(min),127);

for i:=1 to 2*m do min[i,i]:=0;

for len:=2 to m do

for i:=1 to 2*m-len+1 do

begin

be:=i;

en:=i+len-1;

for k:=be to en do

if min[be,k]+min[k+1,en]+sum[en]-sum[be-1] < min[be,en] then

begin

min[be,en]:=min[be,k]+min[k+1,en]+sum[en]-sum[be-1];

end;

end;

x:=maxlongint;

for i:=1 to m do if min[i,i+m-1]<x then x:=min[i,i+m-1];

inc(ans,x);

exit(sum[m]);

end;

begin

readln(n,m,k);

for i:=1 to n do read(v[i]);

sort(1,n);

fillchar(h,sizeof(h),127);

bv:=1;

bh:=1;

for i:=1 to k do

begin

for j:=1 to m do read(p[j]);

for j:=1 to m do

begin

if v[bv]<=h[bh] then

begin

tmp[ p[j] ]:=v[bv];

inc(bv);

end else

begin

tmp[ p[j] ]:=h[bh];

inc(bh);

end;

end;

h[i]:=calc;

end;

writeln(ans);

end.

#1 3144046cjc@2008-11-12 16:20:00
回复 删除
知道了,是v队列出头了。

加上v[n+1]:=maxlongint;就可以了 。

查看更多回复
提交回复