第一次在洛谷刷到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^91的数组把每个值第一次出现的位置记下来查询的时候直接取下标多快。这个思路本身没有错问题在于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这里栽跟头。因为数组里存的是pairlong 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; vectorpairlong 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^9int理论上能放下但养成用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_maplong 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怎么选很多新手会在这两个容器之间纠结。我这里直接给结论容器单次查询复杂度优点缺点适合场景mapO(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_maplong long, vectorint 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也就安稳收下了。