Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

急需求助:为什么我用快排的程序会超时?

Posted by wxsxg at 2006-02-04 18:08:12 on Problem 1002
这是我的程序:
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:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator