题目描述
略
样例
略
除了二分以外的憨憨思路
(观察数据范围:空间换时间) $O(随便过)$
观察数据范围发现k的范围小的可怜,读入的数中只有在k的范围内的数才对答案产生影响(显而易见
所以考虑用数组upp和loww记录下所有在k范围内的数的起始和结束位置
注意位置从0开始,但是为了便于确定没有出现的数,读入时的下标都从1开始,那么对于查询k,
upp[k]=0就说明k没有出现过,出现过的数输出下标时减一即可
(虽然这样很好写,但我保证这题作为模板题绝对不是这么个解法
时间复杂度
很明显一边读入一边更新数组即可
时间复杂度等于读入读出
C++ 代码
#include<iostream>
#include<cstdio>
using namespace std;
const int maxK=10009;
int n,q,a;
int upp[maxK],loww[maxK];
int main(){
scanf("%d%d",&n,&q);
for(int i=1;i<=n;i++){
scanf("%d",&a);
if(a>=1&&a<=10000){
if(upp[a]==0){
upp[a]=i;
}
loww[a]=i;
}
}
for(int i=1;i<=q;i++){
scanf("%d",&a);
if(upp[a]==0){
puts("-1 -1");
}
else{
printf("%d %d\n",upp[a]-1,loww[a]-1);
}
}
return 0;
}
秀。