点击打开链接http://acm.hdu.edu.cn/showproblem.php?pid=1800
题目意思:有n个士兵每个人有一个水平值,水平高的的人可以教低的人,意思就是求最少的扫帚,那么我们只要知道找到最大重复元素的次数即可,因为相同的人肯定不能共用一个,所以求得最少即为最大的重复次数
注意:前置的0必须要去掉,例如数据
3
0
00
000
输出 3
代码1(直接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;
}
代码2(字典树):
#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;
}
分享到:
相关推荐
HDOJ题目分类HDOJ题目分类HDOJ题目分类
ACM ICPC HDOJ1002
ACM ICPC HDOJ1001
hdoj1001标程
hdoj上的资源,代码有注释,很不错的哦
hdoj1004,解题代码,答案代码,欢迎下载
ACM ICPC HDOJ1008
ACM ICPC HDOJ1003
杭州电子科技大学hdoj1002,大整数相加问题
杭州电子科大HDOJ
ACM ICPC HDOJ1000
hdoj解题代码,题目为1000-1050
c语言 最短路 是hdoj上的一个最短路问题,写的很牛
该题求解在给定的时间及条件下,判断是否存在一条从入口到出口的路。
一些HDOJ上的DP题目的小总结,但愿能帮到那些想专攻DP的人吧
codj,hdoj的源码(50-60题)
hdoj 2013 多校训练3标程+解题报告
搞acm的没有谁不知道杭电题库,但是杭电上的OJ到底该怎么用,对于某些初学者确实一个难题,所以How_to_Use_HDOJ.rar应运而生
HDOJ 源代码 包含几百道HDOJ题目源码
hdoj1005 Number Sequence, 杭州电子科技大学oj题目代码