蒟蒻求助!80分,最后一个点RE

P2249 【深基13.例1】查找

Penguin_yuhui @ 2023-10-27 17:53:36

#include<bits/stdc++.h>
using namespace std;
long long n,m;
struct xxx
{
    int wei;//记录位置 
    bool b;//判断这个数是否在数组内出现 
    long long shu;//输入的数据 
}a[100000005];
int main()
{
    scanf("%lld%lld",&n,&m);
    cin>>a[1].shu;//单独保存第一个数 
    a[1].wei=1;//将第一个数的位置设为一 
    a[1].b=1;//第一个数存在
    for(int i=2;i<=n;i++)
    {
        cin>>a[i].shu;
        if(a[i].shu==a[i-1].shu) a[i].wei=a[i-1].wei;//如果一个数等于前一个数,则传承第一个位置 
        else a[i].wei=i;//否则等于当前位置 
        a[a[i].shu].b=1;//记录此数出现过 
    }
    for(int i=1;i<=m;i++)
    {
        long long x;
        scanf("%lld",&x);
        if(a[x].b==0) //如果这个数没出现过 
        {
            cout<<-1<<' ';
            continue;
        }
        long long l=1,r=n;//二分 
        while(l<=r)
        {
            int mid=(l+r)/2;
            if(a[mid].shu==x) //如果找到想找的那个数 
            {
                //输出保存的位置 
                printf("%lld ",a[mid].wei);
                break;  
            }   
            else if(a[mid].shu>x) r=mid-1;
            else l=mid+1;
        }   
    }
    return 0;
} 

by Starry_dream @ 2023-10-27 18:37:31

这题要用二分做


|