| ||||||||||
| Online Judge | Problem Set | Authors | Online Contests | User | ||||||
|---|---|---|---|---|---|---|---|---|---|---|
| Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest | |||||||||
急需求助:为什么我用快排的程序会超时?这是我的程序:
const
inputfile='ex.in';
map:array[1..26] of integer=(2,2,2,3,3,3,4,4,4,5,5,5,6,6,6,7,0,7,7,8,8,8,9,9,9,0);
type
tnum=array[1..7] of integer;
var
f:array[1..100000] of tnum;
times:array[1..100000] of longint;
j,x,l,n,i:longint;
num:tnum;
s:string;
procedure makenum;
var i,j:longint;
begin
j:=0;
for i:=1 to length(s) do if s[i]<>'-' then begin
inc(j);
if s[i] in ['0'..'9'] then num[j]:=ord(s[i])-ord('0')
else num[j]:=map[ord(s[i])-ord('A')+1];
end;
end;
function check(k:longint;num:tnum):longint;
var i,j:longint;
begin
for i:=1 to 7 do if num[i]<f[k,i] then begin
check:=-1;
exit;
end
else if num[i]>f[k,i] then begin
check:=1;
exit;
end;
check:=0;
end;
procedure sort(a,b:longint);
var t,i,j,d:longint;
x:tnum;
begin
if a>=b then exit;
x:=f[a];
i:=a;j:=b;
while i<j do begin
while (i<j) and (check(j,x)<=0) do dec(j);
if (i<j) then begin
f[i]:=f[j];
inc(i);
end;
while (i<j) and (check(i,x)>=0) do inc(i);
if (i<j) then begin
f[j]:=f[i];
dec(j);
end;
f[i]:=x;
end;
if i-1>a then sort(a,i-1);
if i+1<b then sort(i+1,b);
end;
procedure print;
var i,j:longint;
p:boolean;
begin
p:=true;
for i:=1 to l do if times[i]>0 then begin
p:=false;
for j:=1 to 3 do write(f[i,j]);
write('-');
for j:=4 to 7 do write(f[i,j]);
writeln(' ',times[i]+1);
end;
if p then writeln('No duplicates.');
end;
begin
// randomize;
assign(input,inputfile);reset(input);
fillchar(times,sizeof(times),0);
readln(n);
for i:=1 to n do begin
readln(s);
makenum;
f[i]:=num;
end;
close(input);
sort(1,n);
j:=1;
for i:=2 to n do if check(i,f[j])=0 then inc(times[j])
else begin
inc(j);
f[j]:=f[i];
end;
l:=j;
print;
end.
是我的快排写得有问题吗? 还是方法不对?
Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator