蒟蒻80分求调，最后一个TLE。

P2249 【深基13.例1】查找

Doshe @ 2024-08-01 20:12:16

#include <stdio.h>
#include <iostream>
using namespace std;
const int N=1e6+4;
long long int num[N]={0};

int binsearch(int l,int r,long long int q ){
    if(l>r) return -1;
    int mid=(l+r)/2;
    int k=mid;
    if(q==num[mid]) {
        if(binsearch(l,mid-1,q)!=-1){
            return binsearch(l,mid-1,q);
            mid=k;
        }else{
            mid=k;
            return mid;
        }
    }

    if(q>num[mid]){
        return binsearch(mid+1,r,q);
    }else{
        return binsearch(l,mid-1,q);
    }
    return -1;
}

int main(){
    int n,m,i;
    scanf("%d %d",&n,&m);
    for(i=1;i<=n;i++){
        scanf("%lld",&num[i]);
    }
    for(int j=0;j<m;j++){
        long long int q;
        scanf("%lld ",&q);
        printf("%d ",binsearch(1,i,q));
    }
    return 0;
}

大致思路：就是手写了二分，外加了当有多个重复数字时输出第一次出现的位置

by haimingbei @ 2024-08-01 20:18:40

@Doshe

（AC，求关）

#include<bits/stdc++.h>
using namespace std;
int n,m,a[1000005],b[100005],t;
int two(int x){
    int lt=1,rt=n;
    while (lt<rt){
        int mid=lt+(rt-lt)/2;
        if (a[mid]>=x) rt=mid;
        else lt=mid+1;
    }
    if (a[lt]==x) return lt; 
    else return -1;
}
int main(){
    cin>>n>>m;  
    for (int i=1;i<=n;i++)cin>>a[i];
    for (int i=1;i<=m;i++)cin>>b[i];
    for(int i=1;i<=m;i++){
        cout<<two(b[i])<<" ";
    }
    return 0;
}

by Doshe @ 2024-08-01 20:22:19

@haimingbei 我看了其他人有给我类似情况的讨论，我发现你们都是这样找第一次出现的数字的位置的，学到了学到了，谢谢大佬们，已关。