#1失分,求调

P2249 【深基13.例1】查找

Zhang_JY @ 2024-06-28 12:18:44

#include<bits/stdc++.h>
using namespace std;
int n,m;
struct t{
    int data;
    int first;
}a[1000001];
int f(int l,int r,int k){
    if(r==l){
        return -1;
    }
    int mid=(l+r)/2;
//  cout<<"l= "<<l<<' '<<"r= "<<r<<"mid= "<<mid<<'\n'; 

    if(k>a[mid].data){//右
//      cout<<1<<' '<<a[mid].data<<endl;
        return f(mid+1,r,k);
    }
    if(k<a[mid].data){//左
//      cout<<2<<' '<<a[mid].data<<endl;
        return f(l,mid,k);
    }
    if(k==a[mid].data){
    //  return a[mid].data;
        return a[mid].first;
    }
}
int main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        scanf("%d",&a[i].data);
        if(a[i].data!=a[i-1].data){
            a[i].first=i;
        }else{
            a[i].first=a[i-1].first;
        }
    }
//  for(int i=1;i<=n;i++){
//      cout<<a[i].first<<' ';
//  }
//  cout<<endl;
//  cout<<f(1,n,-1);
    for(int i=1;i<=m;i++){
        int t=0;
        cin>>t;
        int p=f(1,n,t);
        cout<<p<<' ';
    }
    return 0;
}

by Evelyn_wsx_star @ 2024-06-28 12:45:08

为什么要这么做?直接二分查找不直接完事?


by Evelyn_wsx_star @ 2024-06-28 12:58:56

@Zhang_JY

#include<stdio.h>

const int M = 1e6 + 5;
int n, m;
int a[M];
int main()
{
    scanf("%d %d", &n, &m);
    for (int i = 1; i <= n; i++) scanf("%d", &a[i]);;
    while (m--)
    {
        int f;
        scanf("%d", &f);

        int l = 1, r = n ;
        while (l<r)
        {
            int mid = l + r>>1;
            if (a[mid]>=f) {
                r = mid; 
            }
            else{
                l = mid + 1;
            } 
        }
        if (a[l] != f){
            printf("-1 ");
        } 
        else {
            printf("%d ", l);
        }
    }
    return 0;
}

by Zhang_JY @ 2024-06-28 17:35:51

@xhsymwx_wsx thanks


by Zhang_JY @ 2024-06-28 17:44:15

@xhsymwx_wsx

已关注


|