C++ 找朋友（friends）

2024-04-26 01:18

文章标签 c++ friends 朋友

本文主要是介绍C++ 找朋友（friends），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

C++ 找朋友（friends）

今天我遇到了一个对于没有学习map的同学非常难的题，题目如下：
题目描述
小学毕业后，同学们都进入了不同的初中，小明非常想念小伙伴们，所以他打算联系小学的同学们。
现在他得到了市内某所初中的所有名单，找出其中小明的小伙伴们。

输入
第一行一个整数n，表示某初中人数。
接下来n行，每行一个字符串，只有小写字母组成，表示该校每个人的拼音。数据保证没有人拼音相同，且已经按照字典序从小到大排序。
第n+2行有一个整数m，表示小明的小伙伴个数。
最后m行，每行一个字符串，只有小写字母组成，表示每个小伙伴的拼音，同样保证没有重复。

输出
输出所有在该校的小伙伴的拼音。
每行一个拼音，顺序按照小伙伴给出的顺序。

样例输入
样例输入1：
3
alice
bob
zhangsan
2
lisi
zhangsan
样例输入2：
2
lisi
zhangsan
3
zhangsan
lisi
alice

样例输出
样例输出1：
zhangsan
样例输出2：
zhangsan
lisi

数据范围限制
对于70%的数据，n<=1000,m<=100
对于100%的数据，n<=100000,m<=10000,每个人拼音长度不超过15。
所有数据，学校学生名单中的姓名，都是按照字典序从小到大排序。

提示
样例1解释：学校有3人，小伙伴有2个，zhangsan在这个学校，因此输出zhangsan
样例2解释：学校有2人，小伙伴有3个，有zhangsan和lisi两人出现在名单中，小伙伴名单输入时lisi在zhangsan后面，所以在输出的小伙伴名单中，lisi排在后面。

题目就这样，不知道map的小伙伴也许就会想输入，然后线性查找。
也许你觉得没什么问题，但你一想，时间复杂度是O(m*n)，最大是100000×10000=10e。如此恐怖的数字，绝对是TLE，所以就需要用到——map
现在讲讲什么是map。
int、char、bool等类型大家肯定都知道，每一个变量（或常量）都只有一种类型。但你想过有两种类型的变量数组么？

map<int,char>cmp;

这句代码定义了数组cmp，尖括号中的“int”和“char”声明了这个数组有int和char两种类型。
但这个map和struct还是有区别的，struct是自定义类型，map是多类型数组。
接下来写个实例：

#include<iostream>
using namespace std;
map<int,char>cmp;
int main(）
{cmp[0]=123456;cout<<cmp[0]<<endl;cmp[1]='A';cout<<cmp[1]<<endl;cmp[2]=345;cout<<cmp[2]<<endl;for(int i=0;i<3;i++) cout<<cmp[i]<<endl;return 0;
}

看了这些代码，你第一反应就是输出123456，A，345，2,1456A345。但编译器却显示编译错误。原来，调用map需要加上#include<map>库。

#include<iostream>
#include<map>
using namespace std;
map<int,char>cmp;
int main(）
{cmp[0]=123456;cout<<cmp[0]<<endl;cmp[1]='A';cout<<cmp[1]<<endl;cmp[2]=345;cout<<cmp[2]<<endl;for(int i=0;i<3;i++) cout<<cmp[i]<<endl;return 0;
}

现在是不是正确了呢？
接着讲题：你只要把输入的每个人都存为true，再判断小明给出的各个同学下标是否为true，是的话存到ans数组里。
接下来上代码：

#include<iostream>
#include<map>
using namespace std;
int n,m,k;
string a,ans[100005];
map<string,bool> str;//定义一个string、bool共同的数组str
int main()
{cin>>n;for(int i=0;i<n;i++){cin>>a;//输入字符串str[a]=true;//将字符串下标标记为true}cin>>m;for(int i=0;i<m;i++){cin>>a;//输入小明同学名字if(str[a]==true) //判断小明同学下标是否为true{ans[k]=a;//存储答案k++;//答案数量++}}for(int i=0;i<k;i++) cout<<ans[i]<<endl;//输出答案return 0;
}