【题意】
给定不超过1000000个不多于10000种的字符串,求每种字符串占总数的百分比,结果保留四位小数
【输入】
每行一个字符串,字符串长度不超过30
【输出】
按字典序输出每种字符串,并输出占总数的百分比,结果保留四位小数
快排水过,实际上最好用trie树或者平衡树
program poj2418; var n,i,j,k,tot:longint; str:array [0..1000001] of string[30]; procedure qsort (s,e:longint); var i,j:longint; k,temp:string; begin if s>=e then exit; i:=s; j:=e; k:=str[(s+e) div 2]; while i<=j do begin while str[i]<k do inc(i); while str[j]>k do dec(j); if i>j then break; temp:=str[i]; str[i]:=str[j]; str[j]:=temp; inc(i); dec(j); end; qsort(s,j); qsort(i,e); end; begin n:=0; while not seekeof do begin inc(n); readln(str[n]); end; if n=0 then exit; qsort(1,n); write(str[1]); k:=1; for i:=2 to n do if str[i]<>str[k] then begin writeln(' ',(i-k)*100/n:0:4); write(str[i]); k:=i; end; writeln(' ',(n-k+1)*100/n:0:4); end.