0分，2个超时，样例正确，求大佬帮助

noraevergreen @ 2024-07-15 18:30:05

#include<bits/stdc++.h>
using namespace std;
const int N=1e6+50;
int n;
int a[N];
int x;

int bs(int l,int r,int x) {
    int mid;
    while(l<=r) {
        mid=(l+r)/2;
        if(a[mid]>=x) r=mid-1;
        else l=mid+1;
    }
    if(a[l]==x) return l;
    else return -1;
}
int main() {
    cin>>n>>x;
    for(int i=1; i<=n; i++)
        cin>>a[i];

    while(x--) {
        cin>>x;
        cout<<bs(1,n,x)<<" ";
    }
}

by weak_in_code @ 2024-07-15 18:37:15

@noraevergreen

二分可以选择这么打，适配大多数题目:

int l=,r=,ans;
while(l<=r)
{
  int mid=(l+r)/2;
  if(check(mid)) l=mid+1,ans=mid;
  else r=mid-1;
}

这道题就是：

#include<bits/stdc++.h>
using namespace std;
const int N=1e6+50;
int n,x;
int a[N];

int bs(int l,int r,int x) {
    int mid,ans=-1;
    while(l<=r) {
        mid=(l+r)/2;
        if(a[mid]==x)
        {
            r=mid-1;
            ans=mid;
        }
        else if(a[mid]>x) r=mid-1;
        else l=mid+1;
    }
    return ans;
}
int main() {
    cin>>n>>x;
    for(int i=1; i<=n; i++)
        cin>>a[i];

    while(x--) {
        int y;
        cin>>y;
        cout<<bs(1,n,y)<<" ";
    }
}

如果最后答案选l的话遇到一些题目卡边界会很麻烦。

by wwhhaatt @ 2024-07-15 18:43:18

倒数第6行

while(x--)

改成

while(m--)

倒数第10行

cin>>n>>x;

改成

cin>>n>>m;

by eleke @ 2024-07-16 09:06:31

直接用二分函数

#include <iostream>
#include <algorithm>
using namespace std;
int a[1000010];

int main()
{
    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= n; i++) cin >> a[i];
    for (int i = 1; i <= m; i++)
    {
        int t;
        cin >> t;
        int pos = lower_bound(a + 1, a + n + 1, t) - a;
            //lower_bound(a + 1, a + n + 1, t);
            //查找a数组中第一个大于等于t的数的位置
        if (t == a[pos]) cout << pos << " ";
        else cout << -1 << " ";
    }
    return 0;
}

by noraevergreen @ 2024-07-16 13:59:40

@weak_in_code 感谢大佬

by noraevergreen @ 2024-07-16 14:00:05

@wwhhaatt 感谢

by noraevergreen @ 2024-07-16 14:00:40

@eleket 感谢