80分求助!!!

P2249 【深基13.例1】查找

caozeheng @ 2024-04-24 17:53:53

用的二分,第六个tle了!!!(难受)


#include<bits/stdc++.h>
using namespace std;
int m1[1000010],m2[100010];
int main(){
    int a,b;
    cin>>a>>b;
    for (int i=1;i<=a;i++) cin>> m1[i];
    for (int i=0;i<b;i++) cin>> m2[i];
    for (int i=0;i<b;i++){
        int l=1,r=a,m;
        while(l<=r){
            m=(l+r)/2;
            if(m1[m]<=m2[i]) l=m+1;
            else r=m-1;
        }
        while(m1[r-1]==m2[i]&&r>1) r--;
        if(m1[r]!=m2[i])cout<<"-1"<<" ";
        else cout<<r<<" ";
    }
    return 0;
}

by hopefire @ 2024-04-24 18:23:24

#include <iostream>
using namespace std;

int m1[1000010], m2[100010];

int main() {
    int a, b;
    cin >> a >> b;

    for (int i = 1; i <= a; i++) 
        cin >> m1[i];

    for (int i = 0; i < b; i++) 
        cin >> m2[i];

    for (int i = 0; i < b; i++) {
        int l = 1, r = a, ans = -1;
        while (l <= r) {
            int m = (l + r) / 2;
            if (m1[m] < m2[i]) 
                l = m + 1;
            else {
                ans = m;
                r = m - 1;
            }
        }
        if (ans != -1 && m1[ans] == m2[i])
            cout << ans << " ";
        else
            cout << "-1 ";
    }
    return 0;
}

by hopefire @ 2024-04-24 18:23:49

@caozeheng 改了一下


by lotsofjelly @ 2024-04-24 18:25:03

没学过binary_search和lower_bound吗?
用上这两个函数试试,一个判断,一个查找


by LRRabcd @ 2024-04-24 19:15:55

#include<iostream>
using namespace std;
int a[1000005];
int n,m;
int find(int x){
    int l=0,r=n+1;
    while(l+1<r){
        int mid=(l+r)/2;
        if(a[mid]>=x){
            r=mid;
        }else{
            l=mid;
        }
    }
    if(a[r]==x){
        return r;
    }
    return -1;
}
int main(){ 
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    a[0]=-10;
    a[n+1]=1.5e9;
    for(int i=1;i<=m;i++){
        int x;
        cin>>x;
        cout<<find(x)<<" ";
    }
    return 0;
}

by yang_h_x_2012 @ 2024-04-28 21:26:53

@B2303huangfeidong 读题cout下标


by yang_h_x_2012 @ 2024-04-28 21:27:48

@yanghexie 好吧我是小丑


|