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

复杂度太高了,你的估计是O(n^2),要O(nlogn)才能过

Posted by sspp at 2004-11-24 10:26:19 on Problem 1002
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:
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