东莞h5网站开发成都园林景观设计公司推荐

东莞h5网站开发,成都园林景观设计公司推荐,海外域名注册网站,静态网站中怎么做图片切换csp信奥赛C标准模板库STL案例应用2 lower_bound实践 题目描述 输入 n n n 个不超过 1 0 9 10^9 109 的单调不减的#xff08;就是后面的数字不小于前面的数字#xff09;非负整数 a 1 , a 2 , … , a n a_1,a_2,\dots,a_{n} a1​,a2​,…,an​#xff0c;然后进行 m m…csp信奥赛C标准模板库STL案例应用2lower_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输入 111 3 1 3 3 3 5 7 9 11 13 15 15 1 3 6输出 11 2 -1说明/提示数据保证1 ≤ n ≤ 1 0 6 1 \leq n \leq 10^61≤n≤1060 ≤ a i , q ≤ 1 0 9 0 \leq a_i,q \leq 10^90≤ai​,q≤1091 ≤ 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返回第一个大于等于目标值的元素位置需要验证找到的元素是否等于目标值代码实现#includebits/stdc.husingnamespacestd;constintN1e610;// 定义数组最大容量略大于10⁶intn,m,a[N];// n: 数字个数m: 询问次数a: 存储数字的数组intmain(){// 关闭同步流提高输入输出速度适用于纯cin/coutios::sync_with_stdio(false);cin.tie(0);cinnm;// 读入n个单调不减的数字下标从1开始题目要求编号从1开始for(inti1;in;i)cina[i];// 处理m次询问while(m--){intx;// 要查找的数字cinx;// lower_bound在[begin, end)范围内查找第一个≥x的元素位置// a1表示数组从下标1开始an1表示结束位置下标n之后// 减去a得到数组下标如果是普通数组减去a得到从0开始的下标// 因为a是指向a[0]的指针所以需要调整为从1开始的下标intanslower_bound(a1,an1,x)-a;// 验证找到的元素是否等于x可能找到的是大于x的元素if(ansnxa[ans])// 添加边界检查更安全coutans ;elsecout-1 ;}return0;}功能分析1.输入处理读取n个有序数字存储到数组a中下标从1开始准备处理m次查询2.二分查找核心lower_bound函数作用在有序区间内二分查找第一个≥x的元素返回指向该元素的指针迭代器时间复杂度O(log n)下标计算// 指针减法得到的是元素之间的偏移量// 因为a指向a[0]所以需要减去a来得到正确下标lower_bound(a1,an1,x)-a例如如果找到a[5]那么a5 - a 5得到下标53.结果验证必须验证找到的元素是否等于目标值x因为lower_bound可能返回第一个大于x的元素位置边界情况查找的值大于数组中所有值会返回an14.时间复杂度预处理O(n) 读取数组每次查询O(log n) 二分查找总体O(m log n) ≈ 10⁵ × log₂(10⁶) ≈ 2×10⁶次操作效率很高5.空间复杂度O(n) 存储数组N10⁶10个int约4MB6.优化措施IO优化使用ios::sync_with_stdio(false)关闭C与C流的同步二分优化直接使用标准库优化过的二分查找内存连续数组存储缓存友好7.边界情况处理查找的值不存在返回-1查找的值有多个返回第一次出现的位置lower_bound特性空数组n0时循环不会执行逻辑正确查找值大于所有元素ans n1输出-1查找值小于所有元素可能找到a[1]验证后输出-1各种学习资料助力大家一站式学习和提升#includebits/stdc.husingnamespacestd;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 点击跳转· 文末祝福 ·#includebits/stdc.husingnamespacestd;intmain(){cout跟着王老师一起学习信奥赛C;cout 成就更好的自己 ;cout csp信奥赛一等奖属于你! ;return0;}