算法笔记P1918 保龄球 (STL map 离散映射)1. 题目简述P1918 保龄球 - 洛谷给定N NN堆保龄球每堆有a i a_iai​个球位置编号为1 ∼ N 1 \sim N1∼N。有Q QQ次询问每次给出一个数字M MM问哪一堆的球数恰好是M MM。数据范围N , Q ≤ 10 5 N, Q \le 10^5N,Q≤105a i ≤ 10 9 a_i \le 10^9ai​≤109。输出要求存在则输出原位置编号不存在输出0 00。2. 核心代码 (C 实现)#includebits/stdc.h using namespace std; typedef long long ll; ll N; // 堆数 mapll, ll Ai; // 核心建立从 球的数量 到 位置编号 的映射 ll Q; // 询问次数 ll M; // 询问的球数 void solve() { // 1. 读入数据并建立映射 if(!(cin N)) return; for(int i 1; i N; i) { ll a; cin a; // Key: 球数 (10^9级别), Value: 位置 (10^5级别) Ai[a] i; } // 2. 处理多次查询 cin Q; for (int i 1; i Q; i) { cin M; // 使用 count 检查是否存在时间复杂度 O(log N) if(Ai.count(M) 1) cout Ai[M] \n; // 使用 \n 避免 endl 频繁刷新缓冲区 else cout 0 \n; } } int main() { // 蓝桥杯必备加速大量数据的输入输出 ios::sync_with_stdio(0); cin.tie(0), cout.tie(0); solve(); return 0; }3. 核心考点与注意事项 核心考点反向索引映射通常我们习惯用“位置”查“数值”本题要求“数值”查“位置”。在数值范围巨大10 9 10^9109而堆数有限10 5 10^5105的情况下使用std::map是最优选择。这里的键值对的插入方式和前面学籍管理的数据插入方式很不一样注意区分。查找效率map底层是红黑树count()和operator[]的复杂度均为O ( log ⁡ N ) O(\log N)O(logN)。总复杂度为O ( ( N Q ) log ⁡ N ) O((NQ) \log N)O((NQ)logN)能稳过10 5 10^5105级别的数据。I/O 优化处理十万级别的输入输出时endl会强制清空缓冲区导致速度剧降。\n是提速的关键。⚠️ 注意事项空间换时间map会带来额外的内存开销。虽然本题内存限制宽裕125MB但在更严苛的题目中若只需计数或存在性判断且内存吃紧可考虑unordered_map平均O ( 1 ) O(1)O(1)但最坏O ( N ) O(N)O(N)。Long Long 的必要性球数10 9 10^9109虽然在int范围内但为了防止计算溢出或题目潜在升级统一使用ll是更稳健的习惯。4. 易错点回顾 (My Mistakes)映射方向倒置最初尝试以位置为键。纠正明确“已知量”作为 Key“待求量”作为 Value。输入作用域错误曾将查询目标M的输入放在了循环外。纠正查询题目必须在每次循环内部实时读入新的目标。语法误区误将成员函数count和erase当作数组访问。纠正函数调用需使用()。不必要的删除曾尝试在查询后使用erase。纠正同一个球数可能被多次询问不可随意删除已建立的索引。