二分查找左边界求调教~~
  • 板块学术版
  • 楼主IKUN_LMX
  • 当前回复5
  • 已保存回复5
  • 发布时间2023/7/13 15:17
  • 上次更新2023/11/3 10:06:30
查看原帖
二分查找左边界求调教~~
947040
IKUN_LMX楼主2023/7/13 15:17

题目传送门:

(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("%ld",&n);
	for(int i=1;i<=n;i++){
		scanf("%ld",&a[i]);
	}
	scanf("%ld",&q);
	for(int i=1;i<=q;i++){
		scanf("%ld",&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:17
加载中...