题目链接：https://www.luogu.org/problemnew/show/P1571
题目描述
虽然Miss Medusa到了北京，领了科技创新奖，但是他还是觉得不满意。原因是，他发现很多人都和他一样获了科技创新奖，特别是其中的某些人，还获得了另一个奖项——特殊贡献奖。而越多的人获得了两个奖项，Miss Medusa就会越眼红。于是她决定统计有哪些人获得了两个奖项，来知道自己有多眼红。
输入格式：
输入第一行，有两个数n,m，表示有n个人获得科技创新奖，m个人获得特殊贡献奖。
第二行，n个正整数，表示获得科技创新奖的人的编号
第三行，m个正整数，表示获得特殊贡献奖的人的编号
输出格式：
输出一行，为获得两个奖项的人的编号，按在科技创新奖获奖名单中的先后次序输出。
输入样例#1：
4 3
2 15 6 8
8 9 2
输出样例#1：
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[], b[];
int main()
{
scanf("%d%d", &n, &m);
for (int i = ; i <= n; i++) { scanf("%d", &a[i]); }
for (int i = ; i <= m; i++) { scanf("%d", &b[i]); mapp[b[i]] = true; }//建立映射关系
for (int i = ; i <= n; i++) if (mapp[a[i]]) cout << a[i] << " ";//如果出现过直接输出
return ;
}
二分查找
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
int n, k, a[], b[];
int main()
{
scanf("%d%d", &n, &k);
for (int i = ; i <= n; i++)scanf("%d", &a[i]);
for (int i = ; i <= k; i++)scanf("%d", &b[i]);
sort(b + , b + + k);
for (int i = ; i <= n; i++)
{
int low = , high = k;
while (low <= high)//二分，查找是否有相同元素
{
int mid = (low + high) / ;
if (b[mid] == a[i])
{
cout << a[i] << " ";
break;
}
else if (b[mid]<a[i])low = mid + ;
else high = mid - ;
}
}
return ;
}
2018-05-27