#1~5WA,#6TLE(样例过了)

P2249 【深基13.例1】查找

y6hz @ 2023-07-31 22:08:14

#include<iostream>
#include<algorithm>
using namespace std;
inline int read(int x) {
    char ch = getchar();
    x = 0;
    while (ch >= '0' && ch <= '9') {
        x = x * 10 + ch - '0';
        ch = getchar();
    }
    return x;
}
inline void write(int x) {
    if(x > 9)
        write(x / 10);
    putchar(x % 10 + '0');
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n, m, q, a[1000000];
    bool b = 0;
    n = read(n), m = read(m);
    for (register int i = 0; i < n; ++i)
        a[i] = read(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;
        q = read(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--;
                write(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 ruye @ 2023-08-03 19:05:59

你的代码放我这里运行不了 看了一眼有可能是

if (a[mid] != q)
            cout << "-1 ";

这里的问题 应该是 if(a[r] != q)


by ruye @ 2023-08-03 19:06:20

#include <bits/stdc++.h>
using namespace std;
#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#define int long long
#define double double long
#define endl '\n'
typedef pair<int, int> pii;
inline int read(){
    char c = getchar();int x = 0, f = 1;
    while(c < '0' || c > '9'){if(c == '-') f = -1; c = getchar();}
    while(c >= '0' && c <= '9'){x = x * 10 + c - '0';c = getchar();}
    return x * f;
}

int dx[] = {0, -1, -1, 0, 1, 1, 1, 0, -1};
int dy[] = {0, 0, 1, 1, 1, 0, -1, -1, -1};

void solve(){
    int n, k;
    cin >> n >> k;
    vector<int> a(n + 1);
    for(int i = 1; i <= n; i ++ ) cin >> a[i];

    while(k -- ){
        int x;
        cin >> x;
        int l = 1, r = n;
        while(l < r){
            int mid = (l + r) / 2;
            if(a[mid] >= x) r = mid;
            else l = mid + 1; 
        }
        if(a[r] != x) cout << -1 << ' ';
        else cout << r  << ' ';
    }
    return ;
}

signed main(){
    IOS;
    int T = 1;
    //cin >> T;
    while(T -- ){
        solve();
    }
    return 0;
}

实在不行 这是我的


by y6hz @ 2023-08-13 21:37:47

好像是快读出问题了


by y6hz @ 2023-08-13 21:38:37

用cin就64了


by y6hz @ 2023-08-13 21:38:52

@ruye


by y6hz @ 2023-08-13 21:40:50

不过还是谢谢你


|