自动搬运

查看原文

来自洛谷，原作者为

	Christopher_Yan AWAY FROM OI

搬运于2025-08-24 21:26:36，当前版本为作者最后更新于2018-03-18 16:29:52，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

虽说这道题标签里写明了二分，然而我还是首先想到了map......毕竟map真的是简单好写。

map做法

#include<bits/stdc++.h>
using namespace std;
int n,m;
map<int,bool> v;
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]);v[b[i]]=true;}//建立映射关系
	for(int i=1;i<=n;i++) if(v[a[i]]) cout<<a[i]<<" ";//如果出现过直接输出
}
return 0;

不过言归正传，我还是冲着二分来写这道题的，这个二分思路不难想，就是将第二个数组排序（第一个数组与输出顺序有关，不能排序），然后挨个二分第一个数组里的数是否存在于第二个数组就好了，时间复杂度O(nlogn)，n<100000，那就不超时啦。

枚举＋二分

#include<bits/stdc++.h>
using namespace std;
int n,m;
int a[101000],b[101000];
bool binary_search(int x)
{
	int l=1,r=m;
    while (l<=r)
	{
        int mid=(l+r)>>1;
        if (b[mid]==a[x])return 1;
        if (b[mid-1]<a[x]&&b[mid+1]>a[x])return 0;
        if (b[mid]>a[x])r=mid;
        else l=mid+1;
    }
    return 0;   
}
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]);
	sort(b+1,b+1+m);
	for(int i=1;i<=n;i++) if(binary_search(i)) printf("%d ",a[i]);
	return 0;
}