【洛谷 P2249】【深基13.例1】查找(向量+lower_bound)

简介: **深基13.例1**是关于查找的编程题,要求在单调不减的整数序列中,对每个查询\( q \)返回其首次出现的位置或输出\-1。输入包含序列大小\( n \),查询次数\( m \),以及序列和查询列表。使用`lower_bound`进行二分查找,找到第一个大于等于目标值的元素位置,若找不到或找到的值不等于目标值,则返回\-1。提供的AC代码中,优化了输入读取,并利用`std::vector`和`std::lower_bound`实现了高效解决方案。

【深基13.例1】查找

题目描述

输入 $n$ 个不超过 $10^9$ 的单调不减的(就是后面的数字不小于前面的数字)非负整数 $a_1,a2,\dots,a{n}$,然后进行 $m$ 次询问。对于每次询问,给出一个整数 $q$,要求输出这个数字在序列中第一次出现的编号,如果没有找到的话输出 $-1$ 。

输入格式

第一行 $2$ 个整数 $n$ 和 $m$,表示数字个数和询问次数。

第二行 $n$ 个整数,表示这些待查询的数字。

第三行 $m$ 个整数,表示询问这些数字的编号,从 $1$ 开始编号。

输出格式

输出一行,$m$ 个整数,以空格隔开,表示答案。

样例 #1

样例输入 #1

11 3
1 3 3 3 5 7 9 11 13 15 15
1 3 6

样例输出 #1

1 2 -1

提示

数据保证,$1 \leq n \leq 10^6$,$0 \leq a_i,q \leq 10^9$,$1 \leq m \leq 10^5$

本题输入输出量较大,请使用较快的 IO 方式。

思路

数据量很大,需要优化读入。lower_bound通过二分查找,返回第一个大于等于某个数的元素的指针。如果指针解引用正好是要找的数,则该指针和向量开头的差值加一为这个数字在序列中第一次出现的编号。如果用lower_bound返回的指针为向量结尾,或对其解引用的值不为查询的值,则没有找到,返回-1。

AC代码

#include <iostream>
#include <vector>
#include <algorithm>
#define AUTHOR "HEX9CF"
using namespace std;

int read(){
   
    char ch;
    int x = 0;
    while((ch < '0' || ch > '9')){
   
        ch = getchar();
    }
    while(!(ch < '0' || ch > '9')){
   
        x = x * 10 + ch - '0';
        ch = getchar();
    }
    return x;
}

int main(){
   
    int n, m;
    vector<int> a;
    n = read();
    m = read();
    for(int i = 0; i < n; i++){
   
        a.push_back(read());
    }
    for(int i = 0; i < m; i++){
   
        if(i){
   
            putchar(' ');
        }
        int t = read();
        vector<int>::iterator lb = lower_bound(a.begin(), a.end(), t);
        if(lb == a.end() || *lb != t){
   
            cout << -1;
        }else{
   
            cout << lb - a.begin() + 1;
        }
    }
    return 0;
}
目录
相关文章
|
5月前
|
存储 算法
【洛谷 P1102】A-B 数对 题解(向量+lower_bound+upper_bound)
这是一个编程题目,要求计算给定正整数序列中满足 \( A - B = C \) 的数对个数。输入包含两行:正整数 \( N \) 和 \( C \),以及一串正整数。输出是满足条件的数对数量。使用排序和二分查找优化算法,代码中给出了 AC 解决方案。样例输入为 \( N=4, C=1 \),序列 \( 1, 1, 2, 3 \),输出为 \( 3 \)。数据范围:\( 1 \leq N \leq 2 \times 10^5 \),\( 0 \leq a_i &lt; 2^{30} \),\( 1 \leq C &lt; 2^{30} \)。
39 0
|
机器学习/深度学习
LeetCode-2055 蜡烛之间的盘子 及库函数 lower_bound 和 upper_bound学习使用
LeetCode-2055 蜡烛之间的盘子 及库函数 lower_bound 和 upper_bound学习使用
华为机试HJ84:统计大写字母个数
华为机试HJ84:统计大写字母个数
华为机试HJ2:计算某字母出现次数
华为机试HJ2:计算某字母出现次数
|
机器学习/深度学习
CF1304B Longest Palindrome(可逆转符号,数学分析,回文串)
CF1304B Longest Palindrome(可逆转符号,数学分析,回文串)
45 0
UVa787 - Maximum Sub-sequence Product(最大连续乘积子串)
UVa787 - Maximum Sub-sequence Product(最大连续乘积子串)
48 0
【基础算法】[PTA]-找出不是两个数组共有的元素
【基础算法】[PTA]-找出不是两个数组共有的元素
|
机器学习/深度学习 Windows
51nod 1258序列求和
51nod 1258序列求和
78 0