为什么#1～#5我都RE啊？

HuangSiHan3116 @ 2024-11-10 12:14:03

#include<bits/stdc++.h>
#define int long long
using namespace std;
long long n,a[90000000],m,q;
signed main(){
    scanf("%lld%lld",&n,&m);
    for(int i=1;i<=n;i++){
        scanf("%lld",&a[i]);
    }
    for(int i=1;i<=m;i++){
        scanf("%lld",&q);
        int b=0;
        for(int j=1;a[j]<=q;j++){
            if(a[j]==q){
                printf("%lld ",j);
                b=1;
                break;
            }
        }
        if(!b) printf("-1 ");
    }
    return 0;
}

by __int1024 @ 2024-11-10 12:23:17

@HuangSiHan3116 第二层循环要判断 j>n 的情况，但是判断了还会TLE（时间复杂度不正确）

by pika_ @ 2024-11-10 12:23:52

1. line 13 的 for循环的第二个条件要加一个 j<=n
2. 1<=n<=1000000, O(n^2)无法通过, 可以使用二分或STL等方法

by HuangSiHan3116 @ 2024-11-10 12:26:19

@__int1024 # 6 我AC了。它不是说后面的数字不小于前面的数字吗？

by HuangSiHan3116 @ 2024-11-10 12:27:39

@__int1024 RE是哈意思?

by HuangSiHan3116 @ 2024-11-10 12:28:41

@pika_ 其他我不会

by __int1024 @ 2024-11-10 12:30:15

@HuangSiHan3116 此题考查二分，正确复杂度应该 O(m\log^2 n) ，但是你 O(n^2) ，一定TLE

by __int1024 @ 2024-11-10 12:30:51

@HuangSiHan3116 一般是数组越界了

by HuangSiHan3116 @ 2024-11-10 12:32:16

@__int1024 数据过多？

by pika_ @ 2024-11-10 12:32:46

O(m log_2 n)

by __int1024 @ 2024-11-10 12:33:18

@HuangSiHan3116 数据太大