机试小课堂丨STL周·例题讲解③《眼红的荔枝》

【声明：本文为原创文章,未经同意,严禁转载和抄袭,违者将追究其法律责任】

苏世机试小课堂，考研机试不再慌！

公主号：苏世学社考研  苏世计算机考研

眼红的荔枝

Time Limit:1000ms   

Memory Limit:65535K

Description

虽然荔枝到了北京，领了科技创新奖，但是他还是觉得不满意。原因是，他发现很多人都和他一样获了科技创新奖，特别是其中的某些人，还获得了另一个奖项——特殊贡献奖。而越多的人获得了两个奖项，荔枝就会越眼红。于是他决定统计有哪些人获得了两个奖项，来知道自己有多眼红。

Input

输入第一行，有两个数n,m，表示有n个人获得科技创新奖，m个人获得特殊贡献奖。

第二行，n个正整数，表示获得科技创新奖的人的编号。

第三行，m个正整数，表示获得特殊贡献奖的人的编号。

Output

输出一行，为获得两个奖项的人的编号，按在科技创新奖获奖名单中的先后次序输出。

注意：本题答案输出一行，最后不需要换行，否则会Presentation Error

Sample Input

4 3

2 15 6 8

8 9 2

Sample Output

2 8

Hint

对于60%的数据，n<=1000，m<=1000。

对于100%的数据，n<=100000，m<=100000，获得奖项的人的编号在2e9以内。

输入数据保证第二行任意两个数不同，第三行任意两个数不同。

答案

①读题:

将这个应用题还原成它的本质，就是依次输出第一行和第二行重复的数字。

②想出思路：

考虑到n,m可能会到100000，简单暴力二层循环会超时，所以用map，用map存储第二行的数字，然后遍历第一行所有数，如果已经被map存储了，就直接输出。

③动手编程：

④测试样例：

拿题目中的样例输入进行测试：

⑤提交代码：

进入下面的链接提交代码：

http://acm.nefu.edu.cn/problemShow.php?problem_id=1686

⑥返回评测结果：

至此，这道题我们就已经完成了。

本题总结

本题用到了map<int,int>，主要是考虑到双层循环来找相同的数字会超时，用map可以理解为先将第二行的数放到里面，然后遍历第一行看看这个数有没有已经放进去了，放进去了就直接输出。

未完待续

苏世学社旗下品牌，专注于计算机考研

计算机考研一手资讯，原创高质量干货

深度的学习分享丨咨询前辈丨个性化指导