题目链接：https://www.luogu.org/problemnew/show/P1571
虽然Miss Medusa到了北京，领了科技创新奖，但是他还是觉得不满意。原因是，他发现很多人都和他一样获了科技创新奖，特别是其中的某些人，还获得了另一个奖项——特殊贡献奖。而越多的人获得了两个奖项，Miss Medusa就会越眼红。于是她决定统计有哪些人获得了两个奖项，来知道自己有多眼红。
输入格式：
输入第一行，有两个数n,m，表示有n个人获得科技创新奖，m个人获得特殊贡献奖。
第二行，n个正整数，表示获得科技创新奖的人的编号
第三行，m个正整数，表示获得特殊贡献奖的人的编号
输出格式：
输出一行，为获得两个奖项的人的编号，按在科技创新奖获奖名单中的先后次序输出。
4 3
2 15 6 8
8 9 2
2 8
对于60%的数据，n<=1000，m<=1000
对于100%的数据，n<=100000，m<=100000，获得奖项的人的编号在2*10^9以内
输入数据保证第二行任意两个数不同，第三行任意两个数不同。
解题分析：
首先这道题可以用map,非常方便。然后也可以用二分查找来做，因为对第二个数组用二分后，整个程序的复杂度为（nlogn）（因为还要遍历一遍第一个数组），而数据范围为10^5，所以可行。
map解法
#include<bits/stdc++.h> using namespace std; int n, m; map<int, bool> mapp; int a[101000], b[101000]; int main() { scanf("%d%d", &n, &m); for (int i = 1; i <= n; i++) { scanf("%d", &a[i]); } for (int i = 1; i <= m; i++) { scanf("%d", &b[i]); mapp[b[i]] = true; }//建立映射关系 for (int i = 1; i <= n; i++) if (mapp[a[i]]) cout << a[i] << " ";//如果出现过直接输出 return 0; }
二分查找
#include<iostream> #include<cstdio> #include<algorithm> using namespace std; int n, k, a[100005], b[100005]; int main() { scanf("%d%d", &n, &k); for (int i = 1; i <= n; i++)scanf("%d", &a[i]); for (int i = 1; i <= k; i++)scanf("%d", &b[i]); sort(b + 1, b + 1 + k); for (int i = 1; i <= n; i++) { int low = 1, high = k; while (low <= high)//二分，查找是否有相同元素 { int mid = (low + high) / 2; if (b[mid] == a[i]) { cout << a[i] << " "; break; } else if (b[mid]<a[i])low = mid + 1; else high = mid - 1; } } return 0; }
2018-05-27
洛谷 P1571 眼红的Medusa【二分查找】 || 【map】
原文：https://www.cnblogs.com/00isok/p/9098156.html