3. 二分查找-变形2 WA

常规
1

二分查找-变形2

TLE 60 PTS

时间限制: 1000ms
空间限制: 262144kB
题目描述

题目描述

二分查找：输入 n 个从小到大的有序数，使用二分查找输出从左往右最后一次出现 m 的位置（计数从 1 开始）。
输入格式
第一行一个整数 n，第二行 n 个整数 ai 表示要查找的有序数列，第三行若干个整数 mi 表示要查找的数字（最多有 S 个）。
输出格式
输出若干个空格分隔的整数，代表 mi 最后一次出现的位置。如果没有这样的数，输出 0。

image
image771×364 11.2 KB

#include <bits/stdc++.h>
 
using namespace std; 
 
const int N=1e6+1;
int a[N],n;
int binary(int x){
  int l=0,r=n;
  while (l+1<r){
    int mid=(r-l)/2+l;
    if(a[mid]>x){
      r=mid;
    }
    else{
      l=mid;
    }
    
  }
  return l;
}

signed main(){
  int x;
  cin >> n;
  for(int i=1;i<=n;i++){
    cin >>a[i];
  }
  while(cin >> x){
    int ans=binary(x);
    if(a[ans]==x){
      cout << ans << " ";
    }
    else{
      cout << 0 << " ";
    }
  }
  return 0;
}

Test 1

Accepted

time: 0ms,memory:3376kb, points: 5

Test 2

Accepted

time: 1ms,memory:3368kb, points: 5

Test 3

Accepted

time: 0ms,memory:3368kb, points: 5

Test 4

Accepted

time: 0ms,memory:3440kb, points: 5

Test 5

Accepted

time: 0ms,memory:3440kb, points: 5

已解锁

Test 6

Wrong Answer

time: 1ms,memory:3444kb, points: 0

解锁

Test 7

Wrong Answer

time: 1ms,memory:3488kb, points: 0

Test 8

Accepted

time: 1ms,memory:3296kb, points: 5

Test 9

Accepted

time: 1ms,memory:3376kb, points: 5

Test 10

Accepted

time: 1ms,memory:3376kb, points: 5

解锁

Test 11

Wrong Answer

time: 31ms,memory:3592kb, points: 0

解锁

Test 12

Wrong Answer

time: 39ms,memory:3748kb, points: 0

Test 13

Accepted

time: 28ms,memory:3616kb, points: 5

Test 14

Accepted

time: 32ms,memory:3728kb, points: 5

Test 15

Accepted

time: 30ms,memory:3728kb, points: 5

解锁

Test 16

Wrong Answer

time: 502ms,memory:3876kb, points: 0

解锁

Test 17

Wrong Answer

time: 122ms,memory:3772kb, points: 0

解锁

Test 18

Wrong Answer

time: 189ms,memory:3752kb, points: 0

解锁

Test 19

Wrong Answer

time: 310ms,memory:3876kb, points: 0

Test 20

Accepted

time: 359ms,memory:3784kb, points: 5

2 个赞
2

我帮你改了一下，你看一下能不能A

#include<bits/stdc++.h>
using namespace std;
int a[1000005];
int main(){
	int n,m;
	cin>>n;
	for(int i=1;i<=n;i++)cin>>a[i];
	while(cin>>m){
		int l=1,r=n;
		while(l+1<r){
			int mid=(l+r)/2;
			if(a[mid]>m)r=mid;
			else  l=mid;
		} 
		if(a[r]==m)cout<<r<<" ";
		else if(a[l]==m)cout<<l<<" ";
		else cout<<0<<" "; 
	}
	 
	return 0;
}
你其实不用写这么多，binary可以不用的，也没必要开long long
1 个赞
3

A了给解决方案

1 个赞