2011-08-23 13:48:52Morris
d885. NOIP2007 1.統計數字 番外篇 (HASH重製)
內容 ：
某次科研调查时得到了n个自然数，每个数均不超过1500000000（1.5*109）。已知不相同的数不超过100000个，现在需要统计这些自然数各自出现的次数，并按照自然数从小到大的顺序输出统计结果。
輸入說明
：
每組输入包含n+1行：
第1行是整数n，表示自然数的个数。
第2~n+1行每行一个自然数。
輸出說明
：
每組输出包含m行（m为n个自然数中不相同数的个数），按照自然数从小到大的顺序输出。每行输出两个整数，分别是自然数和该数出现的次数，其间用一个空格隔开。
範例輸入 ：
8 2 4 2 4 5 100 2 100
範例輸出 ：
2 3 4 2 5 1 100 2
提示
：
100%的数据满足： 1 ≦ n ≦ 5000000，每个数均不超过1 500 000 000（1.5*109）
× 自然數改成>=0的整數
出處
：
HASH | AVL | Splay tree
(管理：morris1028)
作法 : HASH
/**********************************************************************************/
/* Problem: d885 "NOIP2007 1.統計數字 番外篇" from HASH | AVL | Splay tree*/
/* Language: C */
/* Result: AC (498ms, 1180KB) on ZeroJudge */
/* Author: morris1028 at 2011-08-23 13:45:45 */
/**********************************************************************************/
#include<stdio.h>
#include<stdlib.h>
#define HAND (1<<17)-1
int HASH[HAND+1], size;
typedef struct {
int tag, time, next;
} list;
list NODE[100002];
void FreeAll() {
int a;
for(a = 0, size = 1; a <= HAND; a++)
HASH[a] = 0;
}
void insHASH(int n) {
int m = n&HAND;
int pre = 0, now = HASH[m];
while(now) {
if(NODE[now].tag == n) {NODE[now].time++; return;}
else if(NODE[now].tag < n)
pre = now, now = NODE[now].next;
else break;
}
NODE[size].time = 1, NODE[size].tag = n;
NODE[size].next = now;
if(pre) NODE[pre].next = size;
else HASH[m] = size;
size++;
}
int cmp(const void *a, const void *b) {
list *aa, *bb;
aa = (list *)a, bb = (list *)b;
return aa->tag > bb->tag;
}
main() {
int x, n, a;
while(scanf("%d", &n) == 1) {
FreeAll();
for(a = 0; a < n; a++)
scanf("%d", &x), insHASH(x);
qsort(NODE+1, size-1, sizeof(list), cmp);
for(a = 1; a < size; a++)
printf("%d %d\n", NODE[a].tag, NODE[a].time);
}
return 0;
}
上一篇：a225. 明明愛排列
下一篇：d228. kill man