| ||||||||||
| 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 | |||||||||
复杂度太高了,你的估计是O(n^2),要O(nlogn)才能过In Reply To:指针做链表为什么会超时,请帮俺分析分析。 Posted by:xpaq at 2004-11-23 22:37:21 > Program p1002(input,output);
> Type
> telpoint=^telnode;
> telnode=record
> num,times:longint;
> link:telpoint;
> end;
> teltp=record
> head,next,last:telpoint;
> end;
> var
> i,n,tel:longint;
> tellist:teltp;
> s:string;
> c:char;
> Procedure Insert(tel:longint);
> var
> p:telpoint;
> begin
> tellist.next:=tellist.head;
> tellist.last:=tellist.next^.link;
> while (tellist.last<>NIL) and (tellist.last^.num<tel) do begin
> tellist.next:=tellist.last;tellist.last:=tellist.last^.link;
> end;
> if (tellist.last<>NIL) and (tellist.last^.num=tel) then inc(tellist.last^.times)
> else begin
> new(p);p^.num:=tel;p^.times:=1;
> tellist.next^.link:=p;
> p^.link:=tellist.last;
> end;
> end;//procedure Insert
>
> Procedure c2n(var c:char);
> begin
> If (c='A') or (c='B') or (c='C') then c:='2'
> Else if (c='D') or (c='E') or (c='F') then c:='3'
> ELse if (c='G') or (c='H') or (c='I') then c:='4'
> Else if (c='J') or (c='K') or (c='L') then c:='5'
> Else if (c='M') or (c='N') or (c='O') then c:='6'
> Else if (c='P') or (c='R') or (c='S') then c:='7'
> Else if (c='T') or (c='U') or (c='V') then c:='8'
> Else if (c='W') or (c='X') or (c='Y') then c:='9'
> Else c:='0';
> end;//procedure char convert to number
>
> Procedure Print;
> begin
> Str(tellist.next^.num,s);
> while length(s)<7 do s:=Concat('0',s);//Insert('0',s,1);
> writeln(Copy(s,1,3),'-',Copy(s,4,4),' ',tellist.next^.times);
> end;//procedure print;
>
> Begin
> Assign(input,'p1002.in');Reset(input);
> Readln(n);
> New(tellist.head);
> With tellist.head^ do begin num:=0;times:=0;link:=NIL;end;
> tellist.next:=tellist.head;tellist.last:=tellist.next^.link;
> While n>0 do begin
> Readln(s);
> While pos('-',s)<>0 do Delete(s,pos('-',s),1);
> For i:=1 to Length(s) do if not(s[i] in ['0'..'9']) then c2n(s[i]);
> Val(s,Tel);Insert(Tel);
> dec(n);
> end;
> //Print;
> while tellist.head<>NIL do begin
> tellist.next:=tellist.head;
> tellist.head:=tellist.head^.link;
> if tellist.next^.times>1 then Print;
> Dispose(tellist.next);
> end;
> Close(Input);
> End.
Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator