0分求助!!!(lower_bound)

P2249 【深基13.例1】查找

yang_h_x_2012 @ 2024-04-28 21:30:29

0分

#include <bits/stdc++.h>
using namespace std;
int a[1000000];

int main() {
    int n, m;
    cin >> n >> m;
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    while (m--) {
        int x;
        cin >> x;
        if (upper_bound(a, a + n, x) != lower_bound(a,  a + n, x)) {
            cout << lower_bound(a,  a + n, x) - a+1 << " ";

        } else {
            cout << -1;
        }

    }

    return 0;
}

by yang_h_x_2012 @ 2024-04-28 21:48:50

@lczcy1 不加1样例都过不了啊


by Terrible @ 2024-04-28 21:53:30

@yanghexie

没有给序列从小到大排序。

sort(a,a+n); 才具有调用这些二分函数的前提。

另外,查找范围内是否存在特定数字的另外一个专用函数可以参见 https://zh.cppreference.com/w/cpp/algorithm/binary_search。


by Stars_visitor_tyw @ 2024-04-28 21:58:41

@yanghexie 二分的前提是单调性


by yang_h_x_2012 @ 2024-04-28 22:09:32

@taoyiwei17_cfynry 题目保证了单调性啊


by Stars_visitor_tyw @ 2024-04-28 22:10:43

@yanghexie 不好意思看错题了


by yang_h_x_2012 @ 2024-04-28 22:11:05

@Terrible 题目保证了单调性而且我想知道我的代码的语法或逻辑有什么问题啊


by Stars_visitor_tyw @ 2024-04-28 22:11:22

@yanghexie 你可以看下我的手写二分

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

by Terrible @ 2024-04-28 22:55:07

@yanghexie

艹,我还以为是什么很大的错误呢,我傻了。

你的 cout<<-1; 后面没有加空格,加一是为了和题目对齐下标起始位置,这个没问题。

原来是另一个愚蠢的问题。


by yang_h_x_2012 @ 2024-04-29 12:39:17

谢谢


|