怎么过了样例WA64呀

ybc2025_11_LCH @ 2023-01-09 09:54:26

#include <stdio.h>

//const int MOST_NUM = 1e6 + 5;
long long Ask;
long long Num[1000005];
int N, M;

int main(void) {
    int Min = 0, Max, Mid, Tmp;
    scanf("%d", &N);
    for (int i = 0; i < N; ++i) scanf("%lld", &Num[i]);
    for (int i = 0; i < 1; ++i) {
        Tmp = 0;
        scanf("%lld", &Ask);
        Min = 0, Max = N;
        while (Num[Mid] != Ask) {
            ++Tmp;
            Mid = (Min + Max) / 2;
            if (Num[Mid] > Ask) Max = Mid;
            else if (Num[Mid] < Ask) Min = Mid;
            if (Tmp >= 64) {
                printf("-1 ");
                goto OutSide;
            }
        }
        while (Num[--Mid] == Ask) Mid = Mid;
        ++Mid;
        printf("%d ", ++Mid);
        OutSide:;
    }
    return 0;
}

by Offical_ZeldaLT @ 2023-01-09 10:03:05

@ybc2025_11_LCH 12行为什么你的i只有<1?

by Offical_ZeldaLT @ 2023-01-09 10:03:54

@ybc2025_11_LCH 不是输入n和m吗，应该是小于等于m

by Offical_ZeldaLT @ 2023-01-09 10:05:48

#include <stdio.h>

//const int MOST_NUM = 1e6 + 5;
long long Ask;
long long Num[1000005];
int N, M;

int main(void) {
    int Min = 0, Max, Mid, Tmp;
    scanf("%d %d", &N, &M);
    for (int i = 0; i < N; ++i) scanf("%lld", &Num[i]);
    for (int i = 0; i < M; ++i) {
        Tmp = 0;
        scanf("%lld", &Ask);
        Min = 0, Max = N;
        while (Num[Mid] != Ask) {
            ++Tmp;
            Mid = (Min + Max) / 2;
            if (Num[Mid] > Ask) Max = Mid;
            else if (Num[Mid] < Ask) Min = Mid;
            if (Tmp >= 64) {
                printf("-1 ");
                goto OutSide;
            }
        }
        while (Num[--Mid] == Ask) Mid = Mid;
        ++Mid;
        printf("%d ", ++Mid);
        OutSide:;
    }
    return 0;
}

by Offical_ZeldaLT @ 2023-01-09 10:06:32

@ybc2025_11_LCH 第二条说错了，应该是<m就行，你再试试看

by Offical_ZeldaLT @ 2023-01-09 10:08:06

@ybc2025_11_LCH 你的二分好像还有错，我再看看

by Offical_ZeldaLT @ 2023-01-09 10:25:36

@ybc2025_11_LCH 可以用STL里的lower_bound，这个函数可以找到数组中一个数在数组中出现的位置，代码如下，很简洁，给@AndyPomeloMars个关注呗（他逼我的（bushi））

#include <iostream>
using namespace std;

int main(){
    int Num[1000005];
    int N, M;
    scanf("%d %d", &N, &M);
    for (int i = 1; i <= N; ++i) scanf("%d", &Num[i]);
    for (int i = 0; i < M; ++i){
        int Ask;
        scanf("%d",&Ask);
        int ANS = lower_bound(Num+1,Num+N+1,Ask) - Num;
        if(Ask!=Num[ANS]) printf("-1 ");
        else printf("%d ", ANS);
    }
    return 0;
}

by ybc2025_11_LCH @ 2023-01-09 10:33:33

好的，我试试。主要是最近练习二分。

by ybc2025_11_LCH @ 2023-01-09 11:00:49

谢谢你，AC了。