洛谷 1571 眼红的Medusa

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

map做法

#include<bits/stdc++.h>

using namespace std;

int n,m;

map<int,bool> v;

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]);v[b[i]]=true;}//建立映射关系

    for(int i=;i<=n;i++) if(v[a[i]]) cout<<a[i]<<" ";//如果出现过直接输出

}

return ;

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

枚举＋二分

#include<bits/stdc++.h>

using namespace std;

int n,m;

int a[],b[];

bool binary_search(int x)

{

    int l=,r=m;

    while (l<=r)

    {

        int mid=(l+r)>>;

        if (b[mid]==a[x])return ;

        if (b[mid-]<a[x]&&b[mid+]>a[x])return ;

        if (b[mid]>a[x])r=mid;

        else l=mid+;

    }

    return ;

}

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]);

    sort(b+,b++m);

    for(int i=;i<=n;i++) if(binary_search(i)) printf("%d ",a[i]);

    return ;

}

巴特西

洛谷 1571 眼红的Medusa

洛谷 1571 眼红的Medusa

map做法

枚举＋二分

最新文章

热门文章