二分查找左边界求调教~~
查看原帖
二分查找左边界求调教~~
947040
IKUN_LMX楼主2023/7/13 15:27

题目:

(https://www.luogu.com.cn/problem/P2249)

#include<bits/stdc++.h>
using namespace std;
const int  N=10100;int n,q;
int b[N];	
int c[100000001],a[100000001];
int main(){
   scanf("%d",&n);scanf("%d",&q);
   for(int i=1;i<=n;i++){
   	scanf("%d",&a[i]);
   }
   
   for(int i=1;i<=q;i++){
   	scanf("%d",&b[i]);  
   }
   int sum=1;
   int r=n,l=1,mid;
   while(l<=r){
   
   mid=(l+r)/2;		 
   if(a[mid]==b[sum]){
   r=mid-1;
   }
   if(a[mid]>b[sum]){
   r=mid-1;
   }
   if(a[mid]<b[sum]){
   l=mid+1;
   }
   if(a[l]==b[sum]){
   
   c[sum]=l;
   sum++;
   r=n,l=1;
   }
}
for(int i=1;i<=q;i++){
   if(c[i]!=0){
   	printf("%d ",c[i]);
   }
   else{
   printf("%d ",-1);
   }
}
   return 0;
}      
2023/7/13 15:27
加载中...