pascal 统计数字

Question

题目描述某次科研调查时得到了n个自然数，每个数均不超过1500000000（1.5*109）。已知不相同的数不超过10000个，现在需要统计这些自然数各自出现的次数，并按照自然数从小到大的顺序输出统计结果。

数据范围:
40%的数据满足：1<=n<=1000
80%的数据满足：1<=n<=50000
100%的数据满足：1<=n<=200000，每个数均不超过1500 000 000（1.5*109）输入格式输入包含n+1行；
第一行是整数n，表示自然数的个数；
第2~n+1每行一个自然数。输出格式输出包含m行（m为n个自然数中不相同数的个数），按照自然数从小到大的顺序输出。每行输出两个整数，分别是自然数和该数出现的次数，其间用一个空格隔开

Answer 1

这道题是NOIp 2007的复赛提高组第一题吧？ 排序+线性统计的处理即可。
数据规模n在200000因此O(nlogn)排序【即快排或其他高效排序法】可过。数据范围在1,500,000,000<maxlongint=2,147,483,647，所以使用高精度存储完全没有必要。
qsort在一定情况下的最差表现为o(n^2)。
参考程序使用了qsort。
这道题目适合用来初学者练习排序。参考程序
program count;
var
a: array[0..200000] of longint;
n, i, tot: longint;procedure qsort(l, r: longint);
var
ii, jj, kk, mid: longint;
begin
ii := l;
jj := r;
mid := a[(ii+jj) shr 1];
repeat
while a[ii] < mid do inc(ii);
while a[jj] > mid do dec(jj);
if ii <= jj then begin
kk := a[ii];
a[ii] := a[jj];
a[jj] := kk;
inc(ii);
dec(jj);
end;
until ii > jj;
if ii < r then qsort(ii, r);
if jj > l then qsort(l, jj);
end;begin
assign(input, 'count.in');
assign(output, 'count.out');
reset(input);
rewrite(output);
readln(n);
for i := 1 to n do read(a[i]);
qsort(1, n);
tot := 1;
write(a[1]);
for i := 2 to n do begin
if a[i] = a[i-1] then begin
inc(tot);
end else begin
writeln(' ', tot);
write(a[i]);
tot := 1;
end;
end;
writeln(' ', tot);
close(input);
close(output);
end.

Answer 2

先用一个快速排序，然后从小到大输出这个数和和连续为此数的个数。记得不要重复输出了。