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
代码复杂度明显
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
正确的时间复杂度是