csp信奥赛C++标准模板库STL案例应用2
lower_bound实践
题目描述
输入n nn个不超过1 0 9 10^9109的单调不减的（就是后面的数字不小于前面的数字）非负整数a 1 , a 2 , … , a n a_1,a_2,\dots,a_{n}a1,a2,…,an，然后进行m mm次询问。对于每次询问，给出一个整数q qq，要求输出这个数字在序列中第一次出现的编号，如果没有找到的话输出− 1 -1−1。
输入格式
第一行2 22个整数n nn和m mm，表示数字个数和询问次数。
第二行n nn个整数，表示这些待查询的数字。
第三行m mm个整数，表示询问这些数字的编号，从1 11开始编号。
输出格式
输出一行，m mm个整数，以空格隔开，表示答案。
输入输出样例 1
输入 1
11 3 1 3 3 3 5 7 9 11 13 15 15 1 3 6输出 1
1 2 -1说明/提示
数据保证，1 ≤ n ≤ 1 0 6 1 \leq n \leq 10^61≤n≤106，0 ≤ a i , q ≤ 1 0 9 0 \leq a_i,q \leq 10^90≤ai,q≤109，1 ≤ m ≤ 1 0 5 1 \leq m \leq 10^51≤m≤105
本题输入输出量较大，请使用较快的 IO 方式。
思路分析
解题思路
这是一个在单调不减序列中查找元素第一次出现位置的问题。由于序列有序，可以使用二分查找来提高效率。
关键点
- 单调不减性质：后面的数字不小于前面的数字，可以使用二分查找
- 查找要求：找到元素第一次出现的位置（最左位置）
- 数据规模：n≤10⁶，m≤10⁵，需要O(m log n)的算法
算法选择
- 使用C++标准库的
lower_bound函数 lower_bound返回第一个大于等于目标值的元素位置- 需要验证找到的元素是否等于目标值
代码实现
#include<bits/stdc++.h>usingnamespacestd;constintN=1e6+10;// 定义数组最大容量，略大于10⁶intn,m,a[N];// n: 数字个数，m: 询问次数，a: 存储数字的数组intmain(){// 关闭同步流，提高输入输出速度（适用于纯cin/cout）ios::sync_with_stdio(false);cin.tie(0);cin>>n>>m;// 读入n个单调不减的数字，下标从1开始（题目要求编号从1开始）for(inti=1;i<=n;i++)cin>>a[i];// 处理m次询问while(m--){intx;// 要查找的数字cin>>x;// lower_bound在[begin, end)范围内查找第一个≥x的元素位置// a+1表示数组从下标1开始，a+n+1表示结束位置（下标n之后）// 减去a得到数组下标（如果是普通数组，减去a得到从0开始的下标）// 因为a是指向a[0]的指针，所以需要调整为从1开始的下标intans=lower_bound(a+1,a+n+1,x)-a;// 验证找到的元素是否等于x（可能找到的是大于x的元素）if(ans<=n&&x==a[ans])// 添加边界检查更安全cout<<ans<<" ";elsecout<<-1<<" ";}return0;}功能分析
1.输入处理
- 读取n个有序数字存储到数组a中（下标从1开始）
- 准备处理m次查询
2.二分查找核心
lower_bound函数作用：- 在有序区间内二分查找第一个≥x的元素
- 返回指向该元素的指针（迭代器）
- 时间复杂度：O(log n)
下标计算：
// 指针减法得到的是元素之间的偏移量// 因为a指向a[0]，所以需要减去a来得到正确下标lower_bound(a+1,a+n+1,x)-a例如：如果找到a[5]，那么
a+5 - a = 5，得到下标5
3.结果验证
- 必须验证找到的元素是否等于目标值x
- 因为
lower_bound可能返回第一个大于x的元素位置 - 边界情况：查找的值大于数组中所有值，会返回a+n+1
4.时间复杂度
- 预处理：O(n) 读取数组
- 每次查询：O(log n) 二分查找
- 总体：O(m log n) ≈ 10⁵ × log₂(10⁶) ≈ 2×10⁶次操作，效率很高
5.空间复杂度
- O(n) 存储数组，N=10⁶+10个int，约4MB
6.优化措施
- IO优化：使用
ios::sync_with_stdio(false)关闭C与C++流的同步 - 二分优化：直接使用标准库优化过的二分查找
- 内存连续：数组存储，缓存友好
7.边界情况处理
- 查找的值不存在：返回-1
- 查找的值有多个：返回第一次出现的位置（
lower_bound特性） - 空数组：n=0时循环不会执行，逻辑正确
- 查找值大于所有元素：
ans = n+1，输出-1 - 查找值小于所有元素：可能找到a[1]，验证后输出-1
各种学习资料，助力大家一站式学习和提升！！！
#include<bits/stdc++.h>usingnamespacestd;intmain(){cout<<"########## 一站式掌握信奥赛知识! ##########";cout<<"############# 冲刺信奥赛拿奖! #############";cout<<"###### 课程购买后永久学习，不受限制! ######";return0;}- 一、CSP信奥赛C++通关学习视频课：
- C++语法基础
- C++语法进阶
- C++算法
- C++数据结构
- CSP信奥赛数学
- CSP信奥赛STL
- 二、CSP信奥赛C++竞赛拿奖视频课：
- 信奥赛csp-j初赛高频考点解析
- CSP信奥赛C++复赛集训课（12大高频考点专题集训）
- 三、考级、竞赛刷题题单及题解：
- GESP C++考级真题题解
- CSP信奥赛C++初赛及复赛高频考点真题解析
- CSP信奥赛C++一等奖通关刷题题单及题解
详细内容：
1、csp/信奥赛C++，完整信奥赛系列课程（永久学习）：
https://edu.csdn.net/lecturer/7901 点击跳转
2、CSP信奥赛C++竞赛拿奖视频课：
https://edu.csdn.net/course/detail/40437 点击跳转
3、csp信奥赛冲刺一等奖有效刷题题解：
CSP信奥赛C++初赛及复赛高频考点真题解析（持续更新）：https://blog.csdn.net/weixin_66461496/category_12808781.html 点击跳转
- 2025 csp-j 复赛真题及答案解析（最新更新）
- 2025 csp-x(山东) 复赛真题及答案解析（最新更新）
- 2025 csp-x(河南) 复赛真题及答案解析（最新更新）
- 2025 csp-x(辽宁) 复赛真题及答案解析（最新更新）
- 2025 csp-x(江西) 复赛真题及答案解析（最新更新）
- 2025 csp-x(广西) 复赛真题及答案解析（最新更新）
- 2020 ~ 2024 csp 复赛真题题单及题解
- 2019 ~ 2022 csp-j 初赛高频考点真题分类解析
- 2021 ~ 2024 csp-s 初赛高频考点解析
- 2023 ~ 2024 csp-x (山东)初赛真题及答案解析
- 2024 csp-j 初赛真题及答案解析
- 2025 csp-j 初赛真题及答案解析（最新更新）
- 2025 csp-s 初赛真题及答案解析（最新更新）
- 2025 csp-x (山东)初赛真题及答案解析(最新更新)
- 2025 csp-x (江西)初赛真题及答案解析(最新更新)
- 2025 csp-x (辽宁)初赛真题及答案解析(最新更新)
CSP信奥赛C++一等奖通关刷题题单及题解（持续更新）：https://blog.csdn.net/weixin_66461496/category_12673810.html 点击跳转
- 129 道刷题练习和详细题解，涉及：模拟算法、数学思维、二分算法、 前缀和、差分、深搜、广搜、DP专题、 树和图
4、GESP C++考级真题题解：
GESP(C++ 一级+二级+三级)真题题解（持续更新）：https://blog.csdn.net/weixin_66461496/category_12858102.html 点击跳转
GESP(C++ 四级+五级+六级)真题题解（持续更新）：https://blog.csdn.net/weixin_66461496/category_12869848.html 点击跳转
· 文末祝福 ·
#include<bits/stdc++.h>usingnamespacestd;intmain(){cout<<"跟着王老师一起学习信奥赛C++";cout<<" 成就更好的自己！ ";cout<<" csp信奥赛一等奖属于你! ";return0;})
