要点
1.使用双指针
会TLE
2.使用二分的核心在于,你要找哪种性质的边界
3.注意左边界和右边界使用二分的分割方式不同
二分代码(ac):
#include<bits/stdc++.h>
using namespace std;
int n,q,k;
int arr[100010];
int tmp[100010];
int binarySearchRight(int l,int r)
{
while(l<r)
{
int mid=l+r+1>>1;
if(arr[mid]<=k) l=mid;
else r=mid-1;
}
return l;
}
int binarySearchLeft(int l,int r)
{
while(l<r)
{
int mid=l+r>>1;
if(arr[mid]>=k) r=mid;
else l=mid+1;
}
return l;
}
int main()
{
scanf("%d%d",&n,&q);
for(int i=0;i<n;i++)
scanf("%d",arr+i);
while(~scanf("%d",&k))
{
pair<int,int>res=make_pair(-1,-1);
int left=binarySearchLeft(0,n-1);
int right=binarySearchRight(0,n-1);
if(arr[left]==k) res.first=left;
if(arr[right]==k) res.second=right;
printf("%d %d\n",res.first,res.second);
}
return 0;
}
双指针代码(TLE):
int main()
{
scanf("%d%d",&n,&q);
for(int i=0;i<n;i++)
scanf("%d",arr+i);
int k;
while(~scanf("%d",&k))
{
pair<int,int>res=make_pair(-1,-1);
for(int i=0;i<n;i++)
{
if(arr[i]==k)
{
res.first=i;
for(int j=i;j<n;j++)
{
if(arr[j]!=k)
{
res.second=j-1;
break;
}
if(j==n-1&&arr[j]==k) res.second=j;
}
break;
}
}
printf("%d %d\n",res.first,res.second);
}
return 0;
}