HIT2023112282 @ 2024-01-22 22:02:54
#include<bits/stdc++.h>
using namespace std;
int a[1000010],b;
int main()
{
a[0]=-1;a
int n,m,t;
cin>>n>>m;
for(int i=1;i<=n;i++)
{
cin>>a[i];
}
for(int i=1;i<=m;i++)
{
cin>>b;
int l=0,r=n+1;
while(r>l+1)
{
t=(r+l)/2;
if(a[t]==b)
{
break;
}
else if(a[t]<b)
{
l=t;
}
else
{
r=t;
}
}
if(r==l+1)cout<<-1<<" ";
else
{
while(a[t-1]==b)
{
t--;
}
cout<<t<<" ";
}
}
return 0;
}
by Hagasei @ 2024-01-22 22:10:01
@HIT2023112282 36 行处不应暴力向前跳。 因为重复元素可能会很多从而超时。应改为在二分时即使有 a[t]==b
也不退出,并缩短二分右边界。在二分结束之后再判断端点值
by HIT2023112282 @ 2024-01-22 22:21:23
ac了,感谢 @Hagasei
by Hagasei @ 2024-01-22 22:23:41
@HIT2023112282 能点个关注吗谢谢!