全TLE？

eggy__party @ 2024-06-13 21:13:12

#include<bits/stdc++.h>
using namespace std;
const int N=1e6+10;
int a[N],x;
int n,m;
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",&x);
        int l=1,r=n;
        while (l <= r) {
            int mid = (l + r) >> 1;

            if (a[mid]>x)  r = mid;
            else l=mid+1;
        }
        printf("%d ",l);
    }
    return 0;
}

by NullPointerExpection @ 2024-06-13 21:15:49

本题输入输出量较大，请使用较快的 IO 方式。

by keep_shining @ 2024-06-13 21:16:12

调ing

by WEICY123 @ 2024-06-13 21:16:50

@daiym2023 m是10的六次方，n是10的五次方，双for循环最坏情况是O(nm)，是10的11次方，超了

by keep_shining @ 2024-06-13 21:16:56

@NullPointerExpection 跟这没关系，scanf 和 printf 本来就挺快

by keep_shining @ 2024-06-13 21:17:51

@WEICY123 二分是 O(\log_n)，不超时，是二分写错了

by keep_shining @ 2024-06-13 21:19:08

@daiym2023 你这个模版要写 while(l<r)，然后你还没判断 -1 的情况

by keep_shining @ 2024-06-13 21:23:46

@daiym2023

#include<bits/stdc++.h>
using namespace std;
const int N=1e6+10;
int a[N],x;
int n,m;
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",&x);
        int l=1,r=n;
        while (l < r) { //这里 
            int mid = (l + r) >> 1;
            if (a[mid]>=x)  r = mid; //这里 
            else l=mid+1;
        }
        if(a[l]==x)printf("%d ",l);  //判断是否存在 
        else printf("-1 ");
    }
    return 0;
}

by keep_shining @ 2024-06-13 21:24:03

AC 了

by eggy__party @ 2024-06-13 21:31:15

@keep_shining 谢谢

by keep_shining @ 2024-06-13 21:33:37

@daiym2023 不用谢