#6超时求助c++

P2249 【深基13.例1】查找

HIT2023112282 @ 2024-01-22 22:02:54


#include<bits/stdc++.h>
using namespace std;
int a[1000010],b; 
int main()
{
    a[0]=-1;a
    int n,m,t;
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
    }
    for(int i=1;i<=m;i++)
    {
        cin>>b;
        int l=0,r=n+1;
        while(r>l+1)
        {
            t=(r+l)/2;
            if(a[t]==b)
            {
                break;
            }
            else if(a[t]<b)
            {
                l=t;
            }
            else 
            {
                r=t;
            }
        }
        if(r==l+1)cout<<-1<<" ";
        else
        {
            while(a[t-1]==b)
            {
                t--;
            }
            cout<<t<<" ";
        }
    }
    return 0;
}

by Hagasei @ 2024-01-22 22:10:01

@HIT2023112282 36 行处不应暴力向前跳。 因为重复元素可能会很多从而超时。应改为在二分时即使有 a[t]==b 也不退出,并缩短二分右边界。在二分结束之后再判断端点值


by HIT2023112282 @ 2024-01-22 22:21:23

ac了,感谢 @Hagasei


by Hagasei @ 2024-01-22 22:23:41

@HIT2023112282 能点个关注吗谢谢!


|