求助大佬用的二分也超时了

abundan @ 2023-12-18 18:48:05

#include <bits/stdc++.h>
using namespace std;

int a[1000000],b[100000],c[100000];

int main() 
{
    int n,m;
    scanf("%d %d",&n,&m);
    for(int i=0;i<n;i++)scanf("%d",&a[i]);
    for(int i=0;i<m;i++)c[i]=-1;
    for(int j=0;j<m;j++)scanf("%d",&b[j]);

    int left,right,mid;
    for(int i=0;i<m;i++){
        left=0;
        right=n-1;
        while(left<=right){
            mid=(left+right)/2;
            if(b[i]==a[mid])
                c[i]=mid+1;
            else if(b[i]<mid){
                right=mid-1;
            }
            else
                left=mid-1;
        }
    }
    for(int i=0;i<m;i++)printf("%d",c[i]);
    return 0;
}

by ikun_god @ 2023-12-18 19:08:42

我建议用万能的STL(马蜂看不懂)

//莫抄袭，没了AC记录，空悲切！
#include <bits/stdc++.h>
using namespace std;
int main(){
    long long n,m,a[1000001],x;
    cin>>n>>m;
    for (int i=0;i<n;++i){
        cin>>a[i];
    }
    while (m>0){
        cin>>x;
        long long ans=lower_bound(a,a+n,x)-a;
        if (a[ans]!=x){
            cout<<-1<<" ";
        }else{
            cout<<ans+1<<" ";
        }
        m-=1;
    }
}

by ikun_god @ 2023-12-18 19:13:26

还有你为什么left是-1？不应该是加一嘛？

by ikun_god @ 2023-12-18 19:16:48

另外不是数组a比数组b嘛？怎么21行就变成了

b[i]<mid

建议改改

by ikun_god @ 2023-12-18 19:20:52

还有在这次已经找到的情况下早就可以结束了

所以我建议在代码21行哪里直接break。

by ikun_god @ 2023-12-18 19:21:14

@abundon

by abundan @ 2023-12-18 20:01:05

#include <bits/stdc++.h>
using namespace std;

int a[1000000],b[100000],c[100000];

int main() 
{
    int n,m;
    scanf("%d %d",&n,&m);
    for(int i=0;i<n;i++)scanf("%d",&a[i]);
    for(int i=0;i<m;i++)c[i]=-1;
    for(int j=0;j<m;j++)scanf("%d",&b[j]);

    int left,right,mid;
    for(int i=0;i<m;i++){
        left=0;
        right=n-1;
        while(left<=right){
            mid=(left+right)/2;
            if(b[i]==a[mid]){
                c[i]=mid+1;
                break;
            }
            else if(b[i]<a[mid]){
                right=mid-1;
            }
            else
                left=mid+1;
        }
    }
    for(int i=0;i<m;i++)printf("%d",c[i]);
    return 0;
}

@ikun_god 大佬我改了之后，全wa了 然后是我还没学到STL

by ikun_god @ 2023-12-20 12:14:01

我建议你18行改成left<right

by ikun_god @ 2023-12-20 12:14:13

@abundon