——————————————————————————————
题意概括
实在懒得概括了,真的是浅显易懂到了极点……
——————————————————————————————
思路分析
这道题普通的做法肯定不行,毕竟n有1e5那么大,n^2的算法就等着TLE吧
题目的名字也写了,这题考察Lower bound和upper bound函数
——————————————————————————————
但是
我像是那种会乖乖照做的蒟蒻吗
直接暴力循环利用有序的条件,使用二分降低复杂度
计算一下,好像只有 O(m log n)的复杂度欸?!
那我们就愉快的AC这道题吧!
————————————————————————————
AC代码自助
蒟蒻写法,大佬勿喷!
#include<bits/stdc++.h>
#define int long long
using namespace std;
const long long maxn=1e5+10;
int a[maxn];
int n,Q;
int x;
int l,r;
void get(){
l=1;r=n;
while(l + 1 < r){
int mid = (l+r)/2;
if(a[mid] < x){
l = mid;
}
else r = mid;
}
}
void get2(){
l=1;r=n;
while(l + 1 < r){
int mid = (l+r)/2;
if(a[mid] <= x){
l = mid;
}
else r = mid;
}
}
signed main()
{
cin>>n;
for(int i=1;i<=n;i++){
cin>>a[i];
}
cin>>Q;
while(Q--){
cin>>x;
get();
if(a[l] == x) cout<<l<<" ";
else if(a[r] == x) cout<<r<<" ";
else cout<<-1<<" ";
get2();
if(a[r] == x){
cout<<r<<" ";
if(r+1<=n) cout<<r+1<<endl;
else cout<<-1<<endl;
}
else if(a[l] == x) cout<<l<<" "<<r<<endl;
else{
cout<<-1<<" ";
if(a[l] > x) cout<<l<<endl;
else if(a[r] > x)cout<<r<<endl;
else cout<<-1<<endl;
}
}
return 0;
}
共 1 条回复
%%%