在我的代码上改(优化P2249)

P2249 【深基13.例1】查找

wcy20120222 @ 2024-12-10 18:26:06

#include <bits/stdc++.h>
using namespace std;
int a[1000005],b[100005];
int n,m;
int pd(int mid){
    if(a[mid-1]==a[mid]){
        return pd(mid-1);
    }else{
        return mid;
    }
}
int f(int i,int l,int r,int mid){
    for(int j=1;j<=n;j++){
        if(b[i]==a[mid]){
            mid=pd(mid);
            return mid;
        }
        if(b[i]<mid){
            r=mid-1;
            mid=(r+l)/2;
        }else{
            l=mid+1;
            mid=(r+l)/2;
        }
    }
    return -1;
} 
int main() {
    int l,r,mid,s;
    int t=0;
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }

    for(int i=1;i<=m;i++){
        cin>>b[i];
        l=1;
        r=n;
        mid=(l+r)/2;
        t=0;
        cout<<f(i,l,r,mid)<<" ";
    }
    return 0;
}

求改Orz

过题才关!!!


by wcy20120222 @ 2024-12-10 18:27:59

小萌新,Orz


by gzqYES @ 2024-12-10 18:30:00

诶嘿,让我看看


by wcy20120222 @ 2024-12-10 18:35:13

悬关


by neocoding @ 2024-12-10 18:44:46

TLE吗


by neocoding @ 2024-12-10 18:45:53

代码复杂度明显O(n^2m)


by wcy20120222 @ 2024-12-11 17:51:32

@neocoding

求改


by neocoding @ 2024-12-13 16:13:11

@wcy20120222 二分是快速缩小范围,每次取mid,看要找的值在mid左边还是右边,判断出范围后在范围内继续取mid.


by neocoding @ 2024-12-13 16:15:23

而要想快速缩小范围,判断在哪边只需要判断a[mid]和要找的值那个大,a[mid]大就在[l,mid-1]范围找,要找的大就在[mid+1,r]范围找


by neocoding @ 2024-12-13 16:16:33

如果还是不懂,就找我私聊要标程


by neocoding @ 2024-12-13 16:17:48

正确的时间复杂度是 O(nlog_2m)


| 下一页