题目意思:有n个士兵每个人有一个水平值,水平高的的人可以教低的人,意思就是求最少的扫帚,那么我们只要知道找到最大重复元素的次数即可,因为相同的人肯定不能共用一个,所以求得最少即为最大的重复次数
注意:前置的0必须要去掉,例如数据
3
0
00
000
输出 3
法一 map
#include <iostream> #include <cstdio> #include <cstdlib> #include <cstring> #include <string> #include <map> #include <algorithm> using namespace std; //去掉前置的0 string Str(string str){ int mark , i; string temp; if(str.size() == 1)//如果长度为1直接返回 return str; for(i = 0 ; i < str.size() ; i++){ if(str[i] != '0'){ mark = i; break; } } if(i == str.size())//如果 i为 长度说明都是0直接返回一个“0” return "0"; else{ for(int i = mark ; i < str.size() ; i++) temp += str[i];//用temp来存储去0后的字符串 return temp; } } int main(){ int n , max , t; string str , temp; map<string , int>mp; while(scanf("%d" , &n) != EOF){ max = 0; for(int i = 0 ;i < n ; i++){ cin>>str; temp = Str(str); t = ++mp[temp];//注意这里用一个t来存储值,不然超时,map的键值用字符串会很慢 if(max < t) max = t; } cout<<max<<endl; mp.clear();//每次清除mp对象 } return 0; }
法二 字典树
#include <iostream> #include <cstdio> #include <cstring> using namespace std; int ans; char ch[35]; struct Trie{ int num; Trie *child[10]; Trie(){ num = 0; memset(child , 0 , sizeof(child)); } }; Trie *root; int Max(int a , int b){ return a > b ? a : b; } void Trie_Insert(char *str){ Trie *p = root; int i = 0; while(str[i]){ int id = str[i] - '0'; if(p -> child[id] == 0) p -> child[id] = new Trie(); p = p -> child[id]; i++; } p -> num++;//注意这里 p -> num不是放在里面,这样才能对应指向所指的字符串 cout<<"num:"<<p->num<<endl; ans = Max(ans , p -> num); } int main(){ int n; while(cin>>n){ root = new Trie();//这里注意是每一次样列都要进行从新建树 getchar();//消除换行符 ans = 0; for(int i = 0 ; i < n ;i++){ gets(ch); int j = 0; //找到第一个不是0的下标 while(ch[j] == '0'){ j++; } Trie_Insert(ch+j);//传地址过去 } cout<<ans<<endl; } return 0; }