自动搬运

查看原文

来自洛谷，原作者为

	dingcx 不如回头再看一眼题面

搬运于2025-08-24 21:35:36，当前版本为作者最后更新于2020-02-26 22:18:07，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

比赛刚结束，我来水一发题解

暴力解法

这个暴力解法还是蛮好想的。

对于每个询问，从头到尾搜一遍，找到就输出并 break ，如果一直找不到最后输出 $-1$ 。

然而这个的时间复杂度是 $O(nm)$，显然过不了。（代码就不贴了）

正解

这个正解好像也挺好想的

题目说序列单调不减，于是很容易就想到二分。

然而，我很懒，显然不会写二分，那就只能用 STL 自带的二分函数—— upper_bound 和 lower_bound。

这两个函数的作用是二分查找一个数在数组中出现的位置。区别是 upper 返回第一个大于搜索数的位置，而 lower 是第一个大于等于的数的位置。显然这道题用的是 lower。

函数的用法：lower_bound(a.begin(),a.end(),x) 返回第一个大于等于 $x$ 的数的地址。而由于是地址，在最后要 $-a$（也就是减去地址）。

会了这个函数，还有一个问题：怎么判断 $-1$ 的情况？

其实也很简单。如果满足，那么一定有 $x=a[ans]$，所以如果不等那么输出 $-1$ 就行了。

说了这么多，代码也就非常好写了。

代码

下面是完整 AC 代码——

（不能只看这里啊）

#include<cstdio>
#include<algorithm>//用到lower_bound
using namespace std;
const int MAXN=1e6+10;//注意范围
int read(){//快读
	int x=0,f=1;
	char c=getchar();
	while(c<'0'||c>'9'){
		if(c=='-') f=-1;
		c=getchar();
	}
	while(c>='0'&&c<='9'){
		x=x*10+c-'0';
		c=getchar();
	}
	return x*f;
}
int a[MAXN];
int main(){
	int n=read(),m=read();//读入
	for(int i=1;i<=n;i++) a[i]=read();
	while(m--){
		int x=read();
		int ans=lower_bound(a+1,a+n+1,x)-a;//二分搜，注意-a
		if(x!=a[ans]) printf("-1 ");//没有，输出-1
		else printf("%d ",ans);//有，输出ans
	}
	return 0;//华丽结束
}

看我这么晚还发题解，总得点个赞再走呀~