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 neocoding @ 2024-12-13 18:07:09
甚至你都可以将询问离线，用尺取法，这种我感觉对新手更友好一点
by wcy20120222 @ 2024-12-15 14:12:34
@neocoding 要代码
by neocoding @ 2024-12-15 21:02:02
二分：
#include <bits/stdc++.h>
using namespace std;
int n,m,a[1000001],x;
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
//freopen(".in","r",stdin);
//freopen(".out","w",stdout);
cin>>n>>m;
for(int i=1;i<=n;i++){
cin>>a[i];
}
for(int i=1;i<=m;i++){
cin>>x;
int l=1,r=n;
while(l<r){
int mid=(l+r)/2;
if(a[mid]>=x) r=mid;
else l=mid+1;
}
if(a[l]==x) cout<<l<<' ';
else cout<<-1<<' ';
}
return 0;
}