黄冈市网站建设_网站建设公司_交互流畅度_seo优化

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 方式。

思路分析

解题思路

这是一个在单调不减序列中查找元素第一次出现位置的问题。由于序列有序，可以使用二分查找来提高效率。

关键点

1. 单调不减性质：后面的数字不小于前面的数字，可以使用二分查找
2. 查找要求：找到元素第一次出现的位置（最左位置）
3. 数据规模：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.优化措施

1. IO优化：使用ios::sync_with_stdio(false)关闭C与C++流的同步
2. 二分优化：直接使用标准库优化过的二分查找
3. 内存连续：数组存储，缓存友好

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;}