P2249---#1WA,#6TLE，求助大佬们

asdfghjklzxcv @ 2023-11-26 18:58:50

#include<iostream>

using namespace std;
int a[1000005];

int two(int a[],int left,int right,int s)
{
    int mid;
    int index=-1;
    while(left<=right)
    {
        mid=(left+right)>>1;
        if(a[mid]<s)
        {
            left=mid+1;
        }
        else if(a[mid]>s)
        {
            right=mid-1;
        }
        else
        {
            while(a[mid-1]==a[mid])
            {
                mid--;
            }
            index=mid+1;
            break;
        }
    }
    return index;   
}

int main()
{
    int n,m,i,k;
    cin>>n>>m;
    for(i=0;i<n;i++)
    {
        cin>>a[i];
    }
    while (m--)
    {
        cin >> k;
        cout <<two(a, 0, n-1, k) <<" ";
    }
    return 0;
}

by Yemuua @ 2023-11-28 23:24:00

第三个else是暴力搜索边界，我第一次测试也有这个问题，换一种搜索边界的方法就可以

by liuyongqing @ 2023-11-30 21:00:37

@Yemuua 大佬 第一个测试点是什么

by Yemuua @ 2023-11-30 22:46:04

@liuyongqing 贴份我的吧，第一个测试用例我没看过。

#include <stdio.h>
#include <math.h>
#include <string.h>
#include <stdlib.h>
int* a;
int* b;
int n;
int qs(int start, int end, int t) {
    int l = start, r = end;
    while (l <= r) {
        int mid = l + (r - l) / 2;
        if (a[mid] < t) {
            l = mid + 1;
        }
        else {
            r = mid - 1;
        }
    }
    if (a[l] == t)return l;
    return -1;
}
int main(){
    int m;
    scanf("%d%d", &n, &m);
    a = (int*)malloc(n * sizeof(int));
    b = (int*)malloc(m * sizeof(int));
    for (int i = 0; i < n; i++) {
        scanf("%d", a + i);
    }
    for (int i = 0; i < m; i++) {
        scanf("%d", b + i);
        int x = qs(0, n - 1, b[i]);
        if (x == -1) {
            printf("%d ", -1);
        }
        else {
            printf("%d ", x + 1);
        }
    }
    free(a);
    free(b);
    return 0;
}
```稍微对照看看

by liuyongqing @ 2023-12-02 15:55:54

@Yemuua 谢谢大佬，我明白了