84分求助，第一个点tle

易安居士 @ 2024-01-25 12:27:49

#include<bits/stdc++.h>
using namespace std;
int n,a[100000001],m,item;
int confirm(int target,int low,int high)
{
    int mid=(low+high)/2;
    if(target>a[mid])return confirm(target,mid+1,high);
    else if(target<a[mid])return confirm(target,low,mid-1);
    else if(high==low)return high;
    else return confirm(target,low,mid);
}
int halfind(int target,int low,int high)
{
    int mid=(low+high)/2;
    if(low>high)return -1;
    else if(a[mid]<target){
        low=mid+1;
        return halfind(target,low,high);
    }
    else if(a[mid]>target){
        high=mid-1;
        return halfind(target,low,high);
    }
    else {
        if(a[mid]==a[mid-1])return confirm(target,low,mid-1);
        else return mid;
    }
}

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

by ___nyLittleT___ @ 2024-01-25 12:42:37

这个题用二分做的啦

by ___nyLittleT___ @ 2024-01-25 12:43:38

#include<bits/stdc++.h>
using namespace std;
int n,m,x;
int a[1000005];
map<int,bool>vis;
int main(){
    scanf("%d %d",&n,&m);
    for(int i=1;i<=n;i++){
        scanf("%d",&a[i]);
        vis[a[i]]=1;
    }
    while(m--){
        scanf("%d",&x);
        if(!vis[x]){
            printf("-1 ");
            continue;
        }
        int y=lower_bound(a+1,a+1+n,x)-a;
        printf("%d ",y);
    }
    return 0;
}

正常情况下不应该第一个点 T 呀

by 易安居士 @ 2024-01-25 12:46:23

@nyLittleT 刚刚自己改出来问题了，是没考虑第一个点的特判eg: 5 1 0 1 2 3 4 加了特判就ac啦

by 易安居士 @ 2024-01-25 12:47:56

@nyLittleT 谢谢nyLittleT帮忙啦

by 易安居士 @ 2024-01-25 12:48:28

#include<bits/stdc++.h>
using namespace std;
int n,a[100000001],m,item;
int confirm(int target,int low,int high)
{
    int mid=(low+high)/2;
    if(target>a[mid])return confirm(target,mid+1,high);
    else if(target<a[mid])return confirm(target,low,mid-1);
    else if(high==low)return high;
    else return confirm(target,low,mid);
}
int halfind(int target,int low,int high)
{
    int mid=(low+high)/2;
    if(low>high)return -1;
    else if(a[mid]<target){
        low=mid+1;
        return halfind(target,low,high);
    }
    else if(a[mid]>target){
        high=mid-1;
        return halfind(target,low,high);
    }
    else {
        if((a[mid]==a[mid-1])&&mid!=1)return confirm(target,low,mid-1);
        else return mid;
    }
}

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

更正后的ac代码