洛谷 1571 眼红的Medusa

Christopher_Yan · 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;
}