求助最后一个点TLEQAQ
查看原帖
求助最后一个点TLEQAQ
52204
竹取飛翔楼主2020/10/13 10:49

萌新第二次写二分法遇到这迷惑的问题QAQ前面几个点都过了

#include<iostream>
using namespace std;
int a[1000005],b[1000005];
int main()
{
	int m,n,mid;
	cin>>m>>n;
	for(int i=0;i<m;i++) cin>>a[i];//输入数字
	for(int i=0;i<n;i++) cin>>b[i];//输入询问数字
	
	for(int i=0;i<n;i++)
	{
		int left=0,right=m-1;//左右端点
		
		
		while(right>=left)//停止条件
		{
		mid=(left+right)/2;//二分
		
		if (a[mid]>b[i]) 
		{
			right=mid-1;//左移端点
		}
		if (a[mid]<b[i])
		{
			left=mid+1;//右移端点
		} 
		if (a[mid]==b[i])
		{
			break;//找到就跳出
		}
		}//或者两头端点不满足条件时跳出
		
		
		int p=mid;
		if(a[p]!=b[i]) //如果没找到
		{
			cout<<"-1 ";
			continue;//进行下一轮
		}
		if(p>0){//如果有多个数字,找第一个
		
			while(a[p]==b[i]&&a[p-1]==b[i])	p--;
		} 
		cout<<p+1<<" ";//输出,
	}
	return 0;
 } 
2020/10/13 10:49
加载中...