1WA,5TLE,c++

futonghao @ 2023-11-09 20:50:05

#include<bits/stdc++.h>
using namespace std;
int a[1000000],q[100000];
int fun(int left,int right,int i){
    if(left>right)return -1;
    int mid=(left+right)/2;
    if(a[mid]==q[i]){
        while(a[mid]=a[mid-1]){
            mid--;
        }
        return mid+1;
    }
    if(q[i]<a[mid]){
        return fun(left,mid-1,i);
    }else if(q[i]>a[mid]){
        return fun(mid+1,right,i);
    }
}
int main(){
    int n,m;
    cin>>n>>m;
    for(int i=0;i<n;i++){
        cin>>a[i];
    }
    for(int i=0;i<m;i++){
        cin>>q[i];
    }
    for(int i=0;i<m;i++){
        cout<<fun(0,n-1,i)<<" ";
    }
    return 0;
}

by LIUYIFAN5 @ 2023-11-09 21:14:43

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

by LIUYIFAN5 @ 2023-11-09 21:15:06

用这个试试

by Calarence4 @ 2023-11-10 19:38:05

我也是#1WA,#5TLE

#include <bits/stdc++.h>
using namespace std;
int n, q;
int num[(int)1e6];
int main() {
    scanf("%d%d", &n, &q);
    for (int i = 1; i <= n; i++) {
        scanf("%d", &num[i]);
    }
    for (; q-- != 0;) {
        int l = 1, r = n, m = (l + r) / 2;
        int target;
        scanf("%d", &target);
        bool flag = false;
        while (r >= l) {
            if (target == num[m]) {
                flag = true;
                while (target == num[m - 1]) {
                    m--;
                }
                break;
            } else if (target < num[m]) {
                r = m - 1;
                m = (l + r) / 2;
            } else {
                l = m + 1;
                m = (l + r) / 2;
            }
        }
        if (flag == false) {
            printf("-1 ");
        } else {
            printf("%d ", m);
        }
    }
    return 0;
}

by futonghao @ 2023-11-10 21:16:58

@LIUYIFAN5 谢谢