64pts,#1WA,#6TLE

P2249 【深基13.例1】查找

y6hz @ 2023-08-13 21:40:24

#include<iostream>
#include<algorithm>
using namespace std;
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n, m, q, a[1000000];
    bool b = 0;
    cin >> n >> m;
    for (register int i = 0; i < n; ++i)
        cin >> a[i];
    int l = 0, r = n - 1, mid;
    for (register int i = 0; i < m; ++i) {
        b = 0;
        l = 0, r = n - 1, mid = (l + r) / 2;
        cin >> q;
        while (l < r) {
            if (b)
                break;
            if (mid == l || mid == r)
                b = 1;
            if (a[mid] == q) {
                if (mid)
                    while (a[mid - 1] == a[mid])
                        mid--;
                cout << mid + 1;
                cout << ' ';
                break;
            }
            if (a[mid] < q) {
                l = mid;
                mid = (l + r) / 2;
            }
            else if (a[mid] > q) {
                r = mid;
                mid = (l + r) / 2;
            }
        }
        if (a[mid] != q)
            cout << "-1 ";
    }
    return 0;
}

by Literally114514 @ 2023-08-13 21:48:01

@y6hz 逃课做法

#include <iostream>
#include <algorithm>
using namespace std;
int v[1000010];
int main(){
    ios::sync_with_stdio(false);
    int n,m,temp;
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        cin>>v[i];
    }
    for(int i=1;i<=m;i++){
        cin>>temp;
        int ans=lower_bound(v+1,v+n+1,temp)-v;
        if(temp!=v[ans]){
            cout<<"-1"<<" ";
        }else{
            cout<<ans<<" ";
        }
    }
}

by y6hz @ 2023-08-14 08:37:11

@liuzhixing0922 6


by Chlero @ 2023-08-16 09:48:21

我也是#1WA #6TLE

#include<bits/stdc++.h>
using namespace std;
long long n,m,a[1000005];
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);

    cin>>n>>m;
    for(int i=1;i<=n;i++)cin>>a[i];
    while(m--)
    {
        int q;
        cin>>q;

        int l=1,r=n;
        while(l<=r)
        {
            int mid=(l+r)/2;
            if(a[mid]>q)r=mid-1;
            else if(a[mid]==q)
            {
                while(a[mid-1]==q)mid--;
                cout<<mid<<' ';
                goto re;
            }
            else l=mid+1;
        }
        cout<<-1<<' ';
        re:;
    }
    return 0;
}

|