#1-WA,#6-TLE

wangruize88 @ 2024-09-08 11:13:49

#include <stdio.h>
int n , m , q , a[1000001] ;
int find ( int x ) {
    int l = 1 , r = n ;
    while ( l <= r ) {
        int mid = (l+r)>>1 ;
        if ( a[mid] == x ) return mid ;
        else if ( a[mid] < x ) l = mid+1 ;
        else r = mid-1 ;
    }
    return -1 ;
}
int main () {
    scanf ( "%d%d" , &n , &m ) ;
    for ( int i = 1 ; i <= n ; i++ ) scanf ( "%d" , &a[i] ) ;
    while ( m-- ) {
        scanf ( "%d" , &q ) ;
        int i = find( q ) ;
        if ( i != -1 ) while( a[i-1] == a[i] ) i-- ;
        printf ( "%d " , i ) ;
    }
    return 0 ;
}

by quxiangyu @ 2024-09-08 11:16:30

@wangruize88 求关注

#include<bits/stdc++.h>
#define ll long long
#define inf 1000000005
#define put putchar('\n')
#define F(i,a,b) for (int i=(a);i<=(b);i++)
#define D(i,a,b) for (int i=(a);i>=(b);i--)
#define R(i,a,b) for (int i=(a);i<(b);i++)
#define go(i,t) for (int i=head[t];i;i=Next[i])
#define sqr(x) ((x)*(x))
#define re register
#define mp make_pair
#define fi first
#define se second
#define pa pair<int,int>
#define pb push_back
#define be begin()
#define en end()
#define ret return puts("-1"),0;
#define N 1300055
#define mod 998244353
#define int ll
using namespace std;
#define gc getchar
inline ll read(){char c=getchar();ll tot=1;while ((c<'0'|| c>'9')&&c!='-') c=getchar();if (c=='-'){tot=-1;c=getchar();}
ll sum=0;while (c>='0'&&c<='9'){sum=sum*10+c-'0';c=getchar();}return sum*tot;}
inline void wr(ll x){if (x<0) {putchar('-');wr(-x);return;}if(x>=10)wr(x/10);putchar(x%10+'0');}
inline void wrn(ll x){wr(x);put;}inline void wri(ll x){wr(x);putchar(' ');}
inline void wrn(ll x,ll y){wri(x);wrn(y);}inline void wrn(ll a,ll b,ll c){wri(a);wrn(b,c);}
//read()读入 ,wr(x) 输出 wrn(x) 输出换行 
int n,m,a[1000005];
int check(int x){
    //输出这个数字在序列中第一次出现的编号，如果没有找到的话输出 -1
    //我们的二分实现的是从左到右第一个>=x的数的位置 
    /*int l=1,r=n,ans=-1;
    while (l<=r){
        int mid=(l+r)/2;
        if (a[mid]>=x) r=mid-1,ans=mid;//如果a[mid]>=x,那么最靠左的>=x的位置一定比mid小或者就是mid
        else l=mid+1;//说明a[l]..a[mid]<x 
    }*/
    int ans;
    ans=lower_bound(a+1,a+n+1,x)-a;
    if (ans==n+1) return -1;
    if (a[ans]==x) return ans;
    else return -1;
}
signed main(){
    n=read();m=read();
    for (int i=1;i<=n;i++) a[i]=read();
    for (int i=1;i<m;i++){
        int t=read();
        printf("%d ",check(t));
    }
    printf("%d",check(read()));
    return 0;
}

by dongzirui0817 @ 2024-09-08 11:24:08

@wangruize88 这题要用二分做