csp信奥赛C++标准模板库STL案例应用6
set实践
题目描述
DL 算缘分算得很烦闷，所以常常到体育馆去打保龄球解闷。因为他保龄球已经打了几十年了，所以技术上不成问题，于是他就想玩点新花招。
DL 的视力真的很不错，竟然能够数清楚在他前方十米左右每个位置的瓶子的数量。他突然发现这是一个炫耀自己好视力的借口——他看清远方瓶子的个数后从某个位置发球，这样就能打倒一定数量的瓶子。
◯ ◯ ◯ \bigcirc \bigcirc \bigcirc◯◯◯
◯ ◯ ◯ ◯ \bigcirc \bigcirc \bigcirc\ \bigcirc◯◯◯◯
◯ \bigcirc◯
◯ ◯ \bigcirc\ \bigcirc◯◯
如上图，每个 “◯ \bigcirc◯” 代表一个瓶子。如果 DL 想要打倒3 33个瓶子就在1 11位置发球，想要打倒4 44个瓶子就在2 22位置发球。
现在他想要打倒m mm个瓶子。他告诉你每个位置的瓶子数，请你给他一个发球位置。
输入格式
第一行包含一个正整数n nn，表示位置数。
第二行包含n nn个正整数a i a_iai，表示第i ii个位置的瓶子数，保证各个位置的瓶子数不同。
第三行包含一个正整数Q QQ，表示 DL 发球的次数。
第四行至文件末尾，每行包含一个正整数m mm，表示 DL 需要打倒m mm个瓶子。
输出格式
共Q QQ行。每行包含一个整数，第i ii行的整数表示 DL 第i ii次的发球位置。若无解，则输出0 00。
输入输出样例 1
输入 1
5 1 2 4 3 5 2 4 7输出 1
3 0说明/提示
【数据范围】
对于50 % 50\%50%的数据，1 ≤ n , Q ≤ 1000 , 1 ≤ a i , m ≤ 1 0 5 1 \leq n, Q \leq 1000, 1 \leq a_i, m \leq 10^51≤n,Q≤1000,1≤ai,m≤105。
对于100 % 100\%100%的数据，1 ≤ n , Q ≤ 100000 , 1 ≤ a i , m ≤ 1 0 9 1 \leq n,Q \leq 100000, 1 \leq a_i, m \leq 10^91≤n,Q≤100000,1≤ai,m≤109。
思路分析
这道题的核心是：给定一组各不相同的数值（每个位置的瓶子数），需要快速查询是否存在某个特定数值，如果存在则返回其位置索引。由于各个位置的瓶子数不同，这本质上是一个查找问题。
关键点：
- 数据结构选择：需要支持快速查找操作
- 复杂度考虑：n和Q都可达100,000，所以每次查询必须是O(log n)或更快
- 数值范围：瓶子数可达10^9，不能使用数组下标直接映射
解法：
使用C++ STL中的set或map实现：
- 将(瓶子数, 位置)作为一个结构体存入
set - 由于瓶子数各不相同，可以直接按瓶子数查找
set内部使用红黑树实现，查找复杂度O(log n)
代码实现
#include<bits/stdc++.h>usingnamespacestd;intn,q;// n: 位置数, q: 查询次数structnode{intc,id;// c: 瓶子数, id: 位置索引// 重载小于运算符，让set按瓶子数c排序booloperator<(constnode&other)const{returnc<other.c;}};set<node>s;// 使用set存储(瓶子数, 位置)对intmain(){// 输入位置数cin>>n;// 读入每个位置的瓶子数for(inti=1;i<=n;i++){intx;cin>>x;// 将瓶子数和位置索引存入sets.insert({x,i});}// 输入查询次数cin>>q;// 处理每次查询while(q--){intm;cin>>m;// 读入目标瓶子数// 在set中查找瓶子数为m的元素// 注意：这里id传入0，因为set只根据c比较autoit=s.find({m,0});if(it!=s.end()){// 找到了，输出对应的位置索引cout<<it->id<<endl;}else{// 没找到，输出0cout<<0<<endl;}}return0;}功能分析
核心功能
- 数据存储：将每个位置的瓶子数及其索引作为整体存入有序集合
- 快速查询：利用二叉搜索树的特性实现O(log n)的查找
- 结果输出：找到时输出位置，未找到时输出0
算法复杂度
- 时间复杂度：
- 插入：O(n log n) - 将n个元素插入set
- 查询：O(Q log n) - Q次查找，每次O(log n)
- 总复杂度：O((n+Q) log n)，完全满足题目要求
- 空间复杂度：O(n) - 存储n个节点
代码特点
- 利用自定义结构体：将瓶子数和位置绑定，便于查找后直接获取位置信息
- 重载运算符：使set能按瓶子数自动排序
- 查找技巧：查找时只需匹配瓶子数，位置设为任意值（这里是0）
适用场景
- 需要快速查找且数据不重复的场景
- 数据量较大（10^5级别）
- 需要同时获取值和其相关信息的场景
各种学习资料，助力大家一站式学习和提升！！！
#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;}
