求助第一个样例

P2249 【深基13.例1】查找

cx401845597 @ 2024-03-31 10:02:53

有没有人知道第一个样例是什么啊?下面的代码没过第一个样例

#include<iostream>
using namespace std;

const int N = 1e6 + 10;
int n, m, arr[N];

int find(int x)
{
    int l = -1, r = n;
    while(l + 1 != r)
    {
        int mid = l + r >> 1;
        if(x > arr[mid]) l = mid;
        else r = mid;
    }
    if(arr[r] == x) return r;
    else return -1;
}

int main()
{
    cin >> n >> m;
    for(int i = 1; i <= n; i ++) scanf("%d", &arr[i]);
    while(m --)
    {
        int x;
        scanf("%d", &x);
        printf("%d ", find(x));
    }

    return 0;
}

by wangtairan114 @ 2024-03-31 10:30:43

我当时好像把arr[0]初始化为-1就过了 @cx401845597


by cx401845597 @ 2024-04-01 23:00:00

@wangtairan114 还真是这样,是什么原理?


by wangtairan114 @ 2024-04-04 14:03:38

@cx401845597 不知道


by torres_c @ 2024-07-01 14:27:18

@cx401845597 arr中的元素有可能会是 0 0 0 0 1 1 1 2 2 2,在这种情况下,如果要查找数字0出现的位置,arr[0]为0会影响查询结果,所以arr[0]需要设置为非0负数


by cx401845597 @ 2024-07-07 11:10:14

@torres_c 太有实力了,确实是这样,感谢。


|