在这里记一下map的遍历~
map<string,int>cnt; std::map<string,int>::iterator it; it=cnt.begin(); while(it!=cnt.end()){ maxx=max(maxx,it->second); it++; }
也可以用C++11中的auto，超级好用~
for(auto it=mp.begin();it!=mp.end;it++){ if(maxx==it->second) cout<<it->first<<endl; }
其中，it->first代表map的第一维元素，it->second代表第二维元素。
接下来做两个水题吧~
AtCoder ABC155 C Poll
**题意：**找出现次数最多的单词，如有多个，按照字典序从小到大输出。
**思路：**用一个map记录每个字符串的次数，遍历一遍即可~
代码：
#include<bits/stdc++.h> using namespace std; const int maxn=1e6+7; map<string,int>mp; string s[maxn]; std::map<string,int>::iterator it; bool cmp(string a,string b){ return a<b; } int main(){ int n;cin>>n; for(int i=1;i<=n;i++){ cin>>s[i]; mp[s[i]]++; } it=mp.begin(); int maxx=-1; while(it!=mp.end()){ maxx=max(maxx,it->second); it++; } //cout<<maxx<<endl; sort(s+1,s+1+n,cmp); for(int i=1;i<=n;i++){ if(mp[s[i]]==maxx){ cout<<s[i]<<endl; mp[s[i]]=0; } } return 0; }
UPC 朋友
题目描述
同学们应该学会多交一些好朋友。朋友关系是相互的，A 是 B 的好朋友，则 B 也是 A 的好朋友。朋友关系是不传递的，A 是 B 的好朋友，B 是 C 的好朋友，但 A 和 C 不一定是好朋友。现在给出某小学部分同学之间的朋友关系，请编程统计朋友最多的人有多少个好朋友。
输入
输入共m+1行。
第1行是两个整数n和m，分别表示同学总人数和朋友关系对数。
第2行到第m+1行，描述了m对朋友关系。每行两个用单个空格隔开的同学姓名。
每个人的姓名仅由小写字母组成，且1≤姓名的长度≤10。
输出
输出共 1 行。
一个整数，表示朋友最多的人有多少个好朋友。
样例输入 Copy
4 3
lucy lily
jam lily
jam peter
样例输出 Copy
2
提示
4个人，3对朋友关系。lucy只有一个朋友lily；jam有两个朋友lily和peter；lily有两个朋友lucy和jam；
peter只有一个朋友jam。
所以lily和jam朋友最多，都是2个。
50%以上的测试点输入数据保证朋友关系没有重复。
100%的测试点输入数据保证2≤n≤100，1≤m≤1000，且没有自己跟自己的朋友关系。
思路： 利用map模拟就行，要注意二维string map的使用
代码：
#include<bits/stdc++.h> using namespace std; const int maxn=1e6+7; map<string,map<string,int> >mp; map<string,int>cnt; std::map<string,int>::iterator it; int main(){ int n,m; string a,b; scanf("%d%d",&n,&m); while(m--){ cin>>a>>b; if(!mp[a][b]){ mp[a][b]=mp[b][a]=1; cnt[a]++; cnt[b]++; } } int maxx=-1; it=cnt.begin(); while(it!=cnt.end()){ maxx=max(maxx,it->second); it++; } printf("%d\n",maxx); return 0; }
还有学长的一种思路是将字符串转为数组下标 思维好强啊orz 传送门
本来以为这个题是并查集，传送门~ 顺便复习一下并查集叭
