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