csp信奥赛C++标准模板库STL案例应用10
map实践
题目描述
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。
题目分析
这是一个典型的查找问题。题目给出每个位置的瓶子数量，然后需要根据给定的瓶子数量m找到对应的位置。关键点在于：
- 每个位置的瓶子数量互不相同
- 需要快速回答多个查询
- 瓶子数量和查询数量都可能达到10^9级别
代码实现
#include<bits/stdc++.h>usingnamespacestd;intn,q;// n: 位置数, q: 查询次数map<int,int>mp;// 哈希表，用于存储瓶子数量到位置的映射intmain(){// 读取位置数量cin>>n;// 读取每个位置的瓶子数量并建立映射for(inti=1;i<=n;i++){intx;cin>>x;mp[x]=i;// 将瓶子数量x映射到位置i// 注意：由于瓶子数量各不相同，不会出现键冲突}// 读取查询次数cin>>q;// 处理每个查询while(q--){intm;// 想要打倒的瓶子数量cin>>m;// 在哈希表中查找是否有瓶子数量为m的位置autoit=mp.find(m);if(it!=mp.end()){// 找到了，输出对应的位置cout<<it->second<<endl;}else{// 没找到，输出0cout<<0<<endl;}}return0;}算法思路详解
核心思想
使用哈希表（C++中的map）建立从瓶子数量到位置的映射。由于题目保证各个位置的瓶子数量不同，可以直接用瓶子数量作为键，位置作为值。
时间复杂度分析
- 建表阶段：O(n log n)，其中n为位置数量
map的插入操作时间复杂度为O(log n)，共插入n次
- 查询阶段：O(q log n)，其中q为查询次数
- 每次查询使用
find函数，时间复杂度为O(log n)
- 每次查询使用
总时间复杂度：O((n+q) log n)，在题目数据范围(1≤n,Q≤100000)下完全可行。
空间复杂度分析
- 使用
map存储n个键值对，空间复杂度为O(n)
为什么使用map而不是数组？
- 瓶子数量m最大可达10^9，无法用数组直接映射
- 瓶子数量各不相同，适合使用键值对存储
- 需要快速查找，哈希表（或平衡二叉搜索树）是最佳选择
功能分析
输入处理
- 读取位置数量n
- 读取n个位置的瓶子数量，建立瓶子数量→位置的映射
- 读取查询次数q
- 依次处理q个查询
查询处理
对于每个查询m：
- 在哈希表中查找键为m的条目
- 如果找到，输出对应的位置（值）
- 如果没找到，输出0
示例解析
输入样例
5 1 2 4 3 5 2 4 7处理过程
- 读取5个位置的瓶子数：[1, 2, 4, 3, 5]
- 建立映射：{1→1, 2→2, 4→3, 3→4, 5→5}
- 第一个查询m=4：
- 在映射中找到4→3，输出3
- 第二个查询m=7：
- 在映射中找不到7，输出0
输出结果
3 0各种学习资料，助力大家一站式学习和提升！！！
#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;}
