二分查找-变形2 TLE60分

常规
1

谁帮我看看
想了好久了

using namespace std; 
const int N=1e5+5;
int main(){
	int n,a[N],m;
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		cin>>a[i];
	}
	while(cin>>m)
	{
	    int lb=1,rb=n,mid;
	    for(int i=n;i>=1;i--)
	    {
	    	int ans=0;
	    	if(a[rb]==m)
			{
				cout<<i<<" ";
				ans++;
				break;
			}else if(rb==1&&ans==0){
			 cout<<"0"<<" ";	
			}
	    	rb--;
		}
    }
	return 0;
}

提交记录
题解
C. 二分查找-变形2
Problem ID: 9434
Contest ID: 5342
必做题
Wrong Answer
10 分
时间限制: 1000ms
空间限制: 262144kB
题目描述
二分查找：输入

n 个从小到大的有序数，使用二分查找输出从左往右最后一次出现
m 的位置（计数从 1 开始）。

输入格式
第一行一个整数

n，第二行

n 个整数 a i
​
表示要查找的有序数列，第三行若干个整数 m i表示要查找的数字（最多有
S 个）。

输出格式
输出若干个空格分隔的整数，代表 m i
最后一次出现的位置。如果没有这样的数，输出 0。

样例
Input 1
7
1 1 3 3 4 4 4
2 3 4 5
Output 1
0 4 7 0

2 个赞
2

在输入时就可以判断

#include<bits/stdc++.h>
using namespace std;
const int n=1e6+5;
int t,flag;
int a[n]; 
int main(){
	int n,m; 
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		cin>>a[i];
		if(a[i]==m){
			t=i;
			flag=1;
		}
	}
	if(flag=1) cout<<t;
	else cout<<0;
}
1 个赞
3

不对啊这个过不了

1 个赞
4

会WA

1 个赞
5

我ac了

1 个赞
6

屏幕截图 2023-11-11 142253
屏幕截图 2023-11-11 1422531842×843 61.3 KB

1 个赞
7 
#include <bits/stdc++.h>
using namespace std;
int main(){
    int mid,left,right,a[1000005],x,f=0;
    cin>>right>>x;
    left=1;
    for(int i=1;i<=right;i++){
        cin>>a[i];
    }
    while(left<right){
        mid=(left+right)/2;
        if(a[mid]<=x) left=mid+1;
        if(a[mid]>x) right=mid;
        f++;
    }
    if(a[left-1]!=x) cout<<"0";
    else cout<<left-1;
    return 0;
}

试试这个？

1 个赞
8

@陈在田

image
image1844×729 154 KB

image
image1852×681 141 KB

1 个赞
9

@桑铃茜 ，你的也不行。。。。。。。。。。。。。

1 个赞
10

题目变了

1 个赞
11

我们用的是老题目，现在是新题目

1 个赞
12 
#include <bits/stdc++.h>
using namespace std; 
int a[100005];
int main(){
	int n;
	cin>>n;
	for(int i=0;i<n;i++){
		cin>>a[i];
	}
	int m;
	while(cin>>m){
	    int l = 0, r = n;
		while (l+1 < r){
  			int mid = l + (r - l)/2;
  			if (a[mid] > m){
    			r = mid;
  			}else{
    			l = mid;
  			}
  		}
  		if(a[l]==m){
  			cout<<l+1<<' '; 
		}else{
			cout <<"0"<<" ";
		}
	}
	return 0;
}
2 个赞