csp信奥赛C++标准模板库STL案例应用6

csp信奥赛C++标准模板库STL案例应用6

set实践

题目描述

DL 算缘分算得很烦闷，所以常常到体育馆去打保龄球解闷。因为他保龄球已经打了几十年了，所以技术上不成问题，于是他就想玩点新花招。

DL 的视力真的很不错，竟然能够数清楚在他前方十米左右每个位置的瓶子的数量。他突然发现这是一个炫耀自己好视力的借口——他看清远方瓶子的个数后从某个位置发球，这样就能打倒一定数量的瓶子。

1. ◯ ◯ ◯ \bigcirc \bigcirc \bigcirc◯◯◯

2. ◯ ◯ ◯ ◯ \bigcirc \bigcirc \bigcirc\ \bigcirc◯◯◯◯

3. ◯ \bigcirc◯

4. ◯ ◯ \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。

思路分析

这道题的核心是：给定一组各不相同的数值（每个位置的瓶子数），需要快速查询是否存在某个特定数值，如果存在则返回其位置索引。由于各个位置的瓶子数不同，这本质上是一个查找问题。

关键点：

1. 数据结构选择：需要支持快速查找操作
2. 复杂度考虑：n和Q都可达100,000，所以每次查询必须是O(log n)或更快
3. 数值范围：瓶子数可达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;}

功能分析

核心功能

1. 数据存储：将每个位置的瓶子数及其索引作为整体存入有序集合
2. 快速查询：利用二叉搜索树的特性实现O(log n)的查找
3. 结果输出：找到时输出位置，未找到时输出0

算法复杂度

• 时间复杂度：
  • 插入：O(n log n) - 将n个元素插入set
  • 查询：O(Q log n) - Q次查找，每次O(log n)
  • 总复杂度：O((n+Q) log n)，完全满足题目要求
• 空间复杂度：O(n) - 存储n个节点

代码特点

1. 利用自定义结构体：将瓶子数和位置绑定，便于查找后直接获取位置信息
2. 重载运算符：使set能按瓶子数自动排序
3. 查找技巧：查找时只需匹配瓶子数，位置设为任意值（这里是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;}