满江红

lr0818 @ 2024-10-05 08:40:06

#include<iostream>
using namespace std;
int main(){
    int n,m;
    cin>>n>>m;
    int a[n+1],b[m+1];
    for (int i=1;i<=n+1;i++) cin>>a[i];
    for (int i=1;i<=n+1;i++){
        cin>>b[i];
        int mmin=1,mmax=n+1,mc=0,s=0;
        while (n--){
            mc=(mmin+mmax)/2;
            if (a[mc]==b[i]){ 
                s=mc; 
                break;
            }
            else if (a[mc]>b[i]) mmax--;
            else mmin++;
        }
        if (s>0) cout<<s<<endl;
        else cout<<-1<<" ";
    }
}

by liujinxv123 @ 2024-10-05 08:43:45

会二分吗

by chrispang @ 2024-10-05 08:48:42

@lr0818 用 map 或 ``unordered_map

by Yxy7952 @ 2024-10-05 08:50:03

@liujinxv123

实在不忍直视

二分中掺杂着循环的味道

by yhzx2023gsq @ 2024-10-05 08:50:54

@lr0818 用二分哩

#include<bits/stdc++.h>
using namespace std;
int n,m,x[10000086],y;
int ef(int t){
    int l=1,r=n,mid;
    while(l+1<r){
        mid=(l+r)/2;
        if(x[mid]>t||x[mid]==t)r=mid;
        else if(x[mid]<t)l=mid;
    }
    if(x[l]==t)return l;
    else if(x[r]==t)return r;
    else return -1;
} 
int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        scanf("%d",&x[i]);
    }
    for(int i=1;i<=m;i++){
        scanf("%d",&y);
        printf("%d ",ef(y));
    }
    return 0;
}

by chrispang @ 2024-10-05 08:57:02

@lr0818

#include <bits/stdc++.h>
#define maxn 1000010
using namespace std;

int n, m, x, pos, a[maxn];
map<int, int>mp;
int main() {
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
    for (int i = n; i >= 1; i--) mp[a[i]] = i;
    for (int i = 1; i <= m; i++) {
        scanf("%d", &x);
        pos = mp[x];
        if(pos) printf("%d ", pos);
        else putchar('-'), putchar('1'), putchar(' ');
    }
    return 0;
}

by chrispang @ 2024-10-05 08:58:47

@lr0818 我寻思你也没在洛谷上提交啊！