第一次在洛谷刷到P1918保龄球时，我差点被题面里那一排球瓶骗了，以为又是个模拟计分题，直到看清数据范围才意识到，这其实是一道非常典型的“大值域查询”题。题目本身不复杂，但要把思路理顺、把代码写稳，顺带把排序二分和哈希两种方案都用明白，这一趟下来收获比想象中大得多。这篇文章写给刚开始刷算法题、想在真实题目里练熟二分查找和哈希表的选手，也适合想快速过掉P1918的刷题党。我会把从暴力到AC的全过程摊开讲，包括我第一次提交时踩进去的两个坑。
1. 第一次读题时的错觉：编号不是1到n，这才是一切坑的源头
1.1 题意一句话就能说清
P1918的场景是这样的：一排保龄球瓶按从左到右的位置编号，第1个、第2个……第n个，每个球瓶上面写着一个数字，这个数字不一定连续，可能很大，也可能重复。裁判会给出若干次询问，每次给一个数字x，要求回答“哪个球瓶上写着这个数字”，如果没有任何球瓶写x，就输出0。
用一组小数据举例：
- n = 5
- 球瓶数字依次为：10, 7, 10, 3, 7
那么询问10，应该输出它的位置。因为10同时出现在第1个和第3个球瓶上，如果题目要求输出最靠前的位置，答案就是1；询问7，答案是2；询问9，没有任何球瓶，输出0。
题目最麻烦的地方在于数据规模：n和询问次数都可以到100000，球瓶上的数字最大可以到10^9。这个范围一出来，很多“直球”做法就当场废了。
1.2 为什么“开一个大数组数数”会当场爆炸
新手最容易产生的想法是：数字最大是10^9，那我就开一个长度为10^9+1的数组，把每个值第一次出现的位置记下来，查询的时候直接取下标，多快。
这个思路本身没有错，问题在于：10^9个int，在C++里就是4GB内存，绝大多数在线评测机的内存限制只有128MB或者256MB，连零头都装不下，更别提还有n和q同时1e5带来的时间压力。就算内存够，这种做法也只是“值域比较友好”时才能用的奢侈方案。
另一个隐藏问题是重复值。如果一个数字出现多次，你需要回答“哪一个位置”，单纯的开数组记录桶数量也办不到。所以这道题一开始就逼着你放弃“拿值当数组下标”的路线，转而思考更通用的“键值映射”或者“排序索引”思路。看清这一点，题目的本质就浮出水面了：一个大数据值域上的“值到位置”查询问题。
2. 方案一：sort加lower_bound，让每个位置跟着值一起走
2.1 核心思路：把“位置”绑在值旁边，再整体排序
既然不能用值当数组下标，那就换一种信息组织方式。我们可以把每个球瓶的信息看作一个二元组“（球瓶上的数字，球瓶位置）”，然后把所有二元组按数字大小排序。排序之后，所有相同的数字会聚在一起，并且因为二元组默认会按位置再排一次序，相同数字内部的位置也是有序的。
这时候，查询某个数字x，就变成了在有序数组里做二分查找，找到第一对满足“数字等于x”的二元组，它的位置就是答案。整个过程不需要任何哈希，只需要一次排序和多次二分。
这其实是一种非常朴素但强大的思想：当你不能通过下标直接访问某个值时，就先把所有候选对象排成一个有序序列，再用二分把“线性寻找”的时间从O(n)压到O(log n)。代价是排序本身要花O(n log n)。
2.2 二分查找时的一个隐蔽细节：为什么构造pair(x, -1)
很多人写这道题的排序二分版时，会在lower_bound这里栽跟头。
因为数组里存的是pair<long long, int>，直接二分查找一个long long类型的x是行不通的，必须构造一个同类型的值去比较。我有很长一段时间都习惯写成make_pair(x, 0)，但这样有个隐患：位置编号是从1开始的，0虽然小于所有真实位置，可万一以后题目改成从0开始编号，这个技巧就会出问题。
更稳妥的做法是构造make_pair(x, -1)作为二分查找的目标。由于pair比较时先比first、再比second，而-1比任何合法位置编号都小，所以二分查找会定位到“第一个first大于等于x”的二元组；如果存在多个值为x的球瓶，它一定指向这些球瓶中最靠左的那个。这样既能判断x是否存在，又天然满足“输出最靠前位置”的需求。
查找完之后，必须加一个边界判断：迭代器没有越界，并且it->first确实等于x，才说明真的找到了值。只看lower_bound返回的结果不判断等于，或者忘了判断it != end，都是提交时常见的RE和WA来源。
2.3 完整C++代码
#include <bits/stdc++.h> using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n; cin >> n; vector<pair<long long, int>> a; a.reserve(n); for (int i = 1; i <= n; i++) { long long v; cin >> v; a.push_back({v, i}); // 值和位置绑定在一起 } sort(a.begin(), a.end()); int q; cin >> q; while (q--) { long long x; cin >> x; // 找到第一个 first >= x 的位置 auto it = lower_bound(a.begin(), a.end(), make_pair(x, -1LL)); if (it != a.end() && it->first == x) { cout << it->second << '\n'; } else { cout << 0 << '\n'; } } return 0; }这里有几个细节值得说明。第一，用long long存球瓶上的数字，虽然题目最大是10^9，int理论上能放下，但养成用long long的习惯可以避免很多边界问题。第二，输出用'\n'而不是endl，后者会强制刷新缓冲区，在q到1e5时会让IO慢上不少。第三，排序后相同数字按位置升序排列，如果题目改成“输出任意一个位置”，这个代码也能AC，因为它输出的就是最靠左的那个。
复杂度上，sort是O(n log n)，每个询问的lower_bound是O(log n)，整体是O((n + q) log n)。在n和q都是1e5时非常轻松。
3. 方案二：哈希映射，近乎O(1)的“查字典”
3.1 用unoredered_map记录第一次出现的位置
如果觉得排序二分还要管理pair有点绕，那就用哈希表。思路更符合直觉：扫描一遍所有球瓶，把“数字 -> 第一次出现的位置”写进表里，之后每次询问直接查表，表里没有就输出0。
为什么只记录第一次出现的位置？因为这道题通常要求输出最靠前的位置。当你从左往右扫描时，第一次遇到某个数字时记下的位置就是最靠左的；后面再遇到相同数字就不用更新了。就算题目允许输出任意位置，记录第一次出现的位置也永远是一个合法答案。
#include <bits/stdc++.h> using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n; cin >> n; unordered_map<long long, int> pos; for (int i = 1; i <= n; i++) { long long v; cin >> v; if (!pos.count(v)) { pos[v] = i; } } int q; cin >> q; while (q--) { long long x; cin >> x; auto it = pos.find(x); if (it != pos.end()) { cout << it->second << '\n'; } else { cout << 0 << '\n'; } } return 0; }这段代码的平均单次查询复杂度是O(1)，预处理是O(n)，整体期望复杂度O(n + q)，是目前三种常见解法里理论最快的。
3.2 find和operator[]千万别随手写错
哈希表方案里最隐蔽的坑，就是unordered_map的operator[]和find用混。
我看到过不少提交写成这样：
if (pos[x]) { cout << pos[x] << '\n'; } else { cout << 0 << '\n'; }单看结果似乎没问题，但这里有个副作用：当x不存在时，pos[x]这个操作会默认插入一个键值对（x, 0）。也就是说，每次查询一个不存在的数字，都会往哈希表里塞一个僵尸条目。如果在for循环里这样用，表会被撑得越来越大，内存和哈希冲突都会恶化；更严重的是，如果值的默认构造无法被比较，甚至可能直接编译或运行出错。
所以查询端坚持两个写法之一：要么用find拿到迭代器再判断，要么用at()并捕获异常（竞赛中不推荐）。P1918的数据量下，find写法是最稳妥的。再补充一句，如果你真的想用operator[]，也应该先count一下，确认存在再取，别让不存在的查询污染表。
3.3 map和unordered_map怎么选
很多新手会在这两个容器之间纠结。我这里直接给结论：
| 容器 | 单次查询复杂度 | 优点 | 缺点 | 适合场景 |
|---|---|---|---|---|
| map | O(log n) | 查询稳定，不会退化，树结构自带有序性 | 常数较大，内存稍高 | 数据量小、追求稳妥、需要有序遍历 |
| unordered_map | 平均O(1) | 期望查询最快，写法直观 | 极端数据可能哈希碰撞退化，常数受实现影响 | 数据量大、时间紧张、数据无恶意构造 |
在洛谷P1918这种题里，两种都能过。唯一要提醒的是：不要在极端情况下盲目相信unordered_map的O(1)，如果你准备参加正式比赛，遇到比较严格的数据构造者，哈希表可能被卡到O(n)的单次查询。这时回退到排序二分反而是最稳妥的。
还有一个折中方案是用sort加unique做离散化，再用一个vector存每个离散化值最靠左的位置，查询时先lower_bound找离散化排名，再取位置。这个方案思路本质上和排序二分一致，但可以省掉pair比较的细节，适合喜欢数组写法的人。
4. 真实评测历程：我是怎么从TLE一路补到AC的
4.1 第一次提交的暴力代码，死得明明白白
我第一次做这道题时，脑子里还没有“值域索引”的概念，顺手写了个最暴力的版本：对每个询问，从头到尾遍历所有球瓶，记录第一个值等于x的位置，找不到就返回0。
代码逻辑很简单，而且在小数据下完全正确：
// 暴力版，仅演示，不要交上去 for (int i = 0; i < q; i++) { long long x; cin >> x; int ans = 0; for (int j = 1; j <= n; j++) { if (ball[j] == x) { ans = j; break; } } cout << ans << '\n'; }问题出在数据规模。当n和q都等于1e5时，最坏情况每次询问都要扫完所有球瓶，总比较次数是1e10次。这个量级在评测机上是不可接受的，我第一次提交的结果就是标准TLE，连半点悬念都没有。
通过这个反面例子，你会更深刻地理解为什么需要“预处理 + 快速查询”的套路。P1918并不是一道出题人故意难为人的题，它只是把“如果你不做任何预处理，查询阶段就会拖垮你”这件事展示得明明白白。
4.2 第二次使用排序二分，却差点被“排序后位置丢失”坑死
抛弃暴力后，我很快想到了排序加二分。但第一次实现时，我犯了一个典型错误：只对值数组排序，没有把位置一起绑住。于是二分确实能在O(log n)时间内找到“存在的值”，可返回的是排序后的下标，不是原始球瓶位置。
换句话说，排序之后原本在第7个位置的数字被挪到了第3个下标，我输出3，答案自然错。这个错误样例可能侥幸能跑对，因为有些小数据里“排序后的下标等于原位置”，但提交后立刻WA。
教训很直白：只要你在做“值到位置”的查询，位置就必须和值一起参与排序，永远不要只排序值，然后把位置弄丢。这也是我文章开头特意强调“把位置钉在值旁边”的原因。
4.3 本地数据实测：三种正确算法差多少
在确认排序二分版AC之后，我又补写了哈希版和离散化数组版，并在本机用n = q = 100000、数字随机分布在1到1e9的数据跑了一遍。时间表现大致如下：
| 方案 | 预处理耗时 | 总耗时（包含查询） | 主观感受 |
|---|---|---|---|
| 暴力 | 0 | 数十秒级别，无法接受 | 卡死 |
| 排序 + lower_bound | 约0.1秒 | 约0.2秒 | 非常舒服 |
| unordered_map | 约0.05秒 | 约0.1秒 | 最快 |
| map | 约0.15秒 | 约0.3秒 | 也很快 |
这里的数字只是我本机的粗略体感，不同评测机会有浮动，但量级关系是稳定的：暴力到1e10级别必死，O((n + q) log n)级别轻松，哈希期望O(n + q)则更轻。如果你在本地测出来的时间和我不一样，不用纠结，只要比赛时限不是特别变态，排序二分和哈希都稳够。
4.4 输入输出的最后一公里
还有一个不太起眼、但容易卡分的点：输入输出。
当n和q都到1e5时，输入的数值数量大约在2e5级别，说多不多说少不少。用cin读入时一定要关同步，也就是写上那句经典咒语：
ios::sync_with_stdio(false); cin.tie(nullptr);如果开着默认同步，某些评测环境下cin会慢到让人怀疑人生。输出同理，不要用endl刷屏，统一用'\n'。这已经是所有C++竞赛代码的常识，但每道题的总提交里，总有人因为少了这几行而TLE，别让P1918成为你的教训现场。
5. 从P1918延伸出去的通用解题思路
5.1 它的本质是“大值域索引”，不是保龄球
做完这道题之后，我最大的感受是：题目包装成保龄球，剥开之后其实是“如何为一个无法直接用数组下标索引的大值域，建立一套快速查询索引”。
这种问题在算法竞赛里反复出现。比如给你一堆人的成绩，成绩范围很大，要求反复查询某个成绩对应的人；比如给你很多坐标点，坐标范围很大，要求判断某个坐标是否存在。凡是遇到这类场景，第一反应就是两个方向：要么对候选数据排序，让二分能上场；要么建立一个哈希映射，让查询变成字典查找。
5.2 如果同一个数字出现多次且要输出全部位置
P1918只要求输出一个位置，很多题解也就只记录最靠左的位置。但如果题目改成“输出某个数字出现的所有位置”，怎么办？
最简单的处理方式是把哈希表的值从int改成vector ：
unordered_map<long long, vector<int>> allPos; for (int i = 1; i <= n; i++) { allPos[v].push_back(i); }查询时直接遍历这个vector。如果还要支持“输出第k次出现的位置”，那就在排序二分方案里用两个lower_bound找到值等于x的区间上下界，然后根据k去定位。这两种延伸在稍难一点的题目里都很常见，练好这道题相当于给那些场景打了个底。
5.3 当“静态查询”升级成“动态修改”时怎么办
P1918的所有球瓶数字在输入后不再改变，属于静态数据，所以排序和哈希都够用。可如果题目允许修改某个球瓶上的数字，又要继续查询，那就不能只用静态索引了，需要上平衡树、线段树或者树状数组之类的动态结构。
这个升级路线不难理解：静态数据用一次排序搞定，动态数据则意味着排序结果可能在每次修改后失效，必须让索引结构支持更新。遇到这类题再去学习线段树不会迟，但先把P1918这种静态索引题做扎实，动态改版你至少能明白“原有方案失效的原因是什么”。
我自己的习惯是，每刷完一道索引题，就在笔记里写一行“这种题的标志是：n和q超过1e5、值域远大于n、只有静态查询”。下次再看到特征类似的题，直接跳过摸索阶段，快速尝试排序二分或者哈希。P1918保龄球这道题，最适合扮演的正是这个“特征样本”的角色。
做完这道题之后，我最大的收获其实不是背会了一个lower_bound模板，而是真正理解了数据组织方式对查询效率的影响。如果你也正在刷这道题，建议别急着看别人的题解，先自己写一版暴力，再改成排序二分，最后用哈希重写一遍，亲身感受一下三种复杂度在同样数据规模下的差别。提交之前再问自己三个问题：位置有没有跟着值走，有没有判断二分边界，输入输出关同步了吗。这三个问题都答上来，P1918也就安稳收下了。
，微信公众号搜一搜云智变 ai)