样例能过,测试点一些TLE,一些WA

P2249 【深基13.例1】查找

yyz0526 @ 2024-03-25 20:48:48

#include <bits/stdc++.h>
using namespace std;
int n,m,a[1000001],q;
bool x;
int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++) scanf("%d",&a[i]);
    for(int i=0;i<m;i++){
        scanf("%d",&q);
        for(int j=1;j<=n;j++){
            if(a[j]==q){
                printf("%d ",j);
                x=false;
                break;
            }
        }
        if(x) printf("-1");
        x=true;
    }
    return 0;
}

by yyz0526 @ 2024-03-25 20:49:29

应该是速度太慢了


by lucy2012 @ 2024-03-25 20:52:00

@yyz0526 建议用二分


by Lg2307 @ 2024-03-25 20:53:51

二分做法:

#include <bits/stdc++.h>
using namespace std;
const int z = 1e6 + 10;
int a[z];
int main(){
    int n,m;
    int x;
    cin >> n >> m;
    for (int i = 1; i <= n; i ++){
        cin >> a[i];
    }
    while (m --){
        cin >> x;
        int l = 1,r = n;
        while (l < r){
            int mid = (l + r) / 2;
            if (a[mid] >= x){
                r = mid;
            }
            else {
                l = mid + 1;
            }
        }
        if (a[l] == x){
            cout << l << " ";
        }
        else {
            cout << "-1" << " ";
        }
    }
    return 0;
}

by lucy2012 @ 2024-03-25 20:57:01

@yyz0526 试试这个函数

int find(int x){
    int r=n+1,l=1,mid;//定r为下限,l为上限
    while(l<r){
        mid=(l+r)/2;//从r和l里取中间数
        if(a[mid]>=x)//如果比要找的数大
            r=mid;//上限减小
        else
            l=mid+1;//下限变大
    }
    if(a[l]==x)//判有没有找到
       return l;
    else
       return -1;
}

by lucy2012 @ 2024-03-25 20:59:15

@yyz0526

int find(int x){
    int r=n+1,l=1,mid;//定r为上限,l为下限
    while(l<r){
        mid=(l+r)/2;//从r和l里取中间数
        if(a[mid]>=x)//如果比要找的数大
            r=mid;//上限减小
        else
            l=mid+1;//下限变大
    }
    if(a[l]==x)//判有没有找到
       return l;
    else
       return -1;
}

搞错了


by yyz0526 @ 2024-03-25 21:01:27

谢谢


|