洛谷 1571 眼红的Medusa

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

map做法

#include
      
       using namespace std;int n,m;map
       
         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<
        
         <<" ";//如果出现过直接输出}return 0;
        
       
      

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

枚举＋二分

#include
      
       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])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;}