825
人物
NYOJ290-動物統計加強版
動物統計加強版
時間限製：3000 ms 內存限製：150000 KB
難度：4
描述
在美麗大興安嶺原始森林中存在數量繁多的物種，在勘察員帶來的各種動物資料中有未統計數量的原始動物的名單。科學家想判斷這片森林中
哪種動物的數量最多，但是由於數據太過龐大，科學家終於忍受不了，想請聰明如你的ACMer來幫忙。
輸入
第一行輸入動物名字的數量N(1= N = 4000000),接下來的N行輸入N個字符串表示動物的名字（字符串的長度不超過10,字符串全為小寫字母，並
且隻有一組測試數據）。
輸出
輸出這些動物中最多的動物的名字與數量，並用空格隔開（數據保證最多的動物不會出現兩種以上）。
樣例輸入
10
boar
pig
sheep
gazelle
sheep
sheep
alpaca
alpaca
marmot
mole
樣例輸出
sheep 3
思路：平常的排序方式已經無法解決，隻能用字典樹來解決，一直不想看字典樹的，因為和麵向對象有關係，今天還是硬著頭皮做了，沒自己
想像的那麼難理解（還好我是學JAVA的），看了網上的模板，揣摩了一番，模仿著寫出來了
AC代碼：
（可以當做字典樹模板）
#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
struct node
{
node *next[26];//node類的26個子類
int count;//每一個類終端的個數
node(){//構造函數，用來初始化數據
memset(next,0,sizeof(next));
count=0;
}
};
int MAX;//用來記錄最出現次數
char flag[20]; //用來記錄出現次數最多的字符串
node *root=new node();//聲明一個初始node類 （這個類決定了以下所有子類，是字典樹的根）
void insert(char *s) //插入新的字符串
{
node *p=root;
int i,k;
for(i=0;s[i];i++){
k=s[i]-'a';
if(p->next[k]==NULL) p->next[k]=new node();//不存在此節點則創建
p=p->next[k];//移向下一個節點
}
p->count++;
if(p->count>MAX){//更新MAX和flag
MAX=p->count;
strcpy(flag,s);
}
}
int main()
{
int n;
char s[15];
scanf("%d",&n);
while(n--)
{
scanf("%s",s);
insert(s);
}
printf("%s %d\n",flag,MAX);
return 0;
}
最後更新：2017-04-03 12:56:30