做算法题的人大概都见过这类题题目不长规则简单但就是有无数人在一个不起眼的边界条件上翻车。UVA1237 / LA4142 Expert Enough? 就是这样一个典型它常被当作入门选手练模拟题的第一道坎也被老选手当成热手的送分题。表面上看标题在问你够不够专业实际是说有一堆汽车厂商各自的定价区间再给你一堆询价单让你判断每个价格对应哪家厂商对应不上、或者同时对应多家都要输出 UNDETERMINED。这篇内容会把题意、算法选型、完整代码和踩坑过程一次讲透适合刚开始刷这类老题库的人也适合想巩固题面约束决定算法思维的人。1. 先读懂题这道询价匹配题到底在考什么1.1 规则拆解输入、输出、判定逻辑题目构造了一个很有画面感的业务场景代理机构接到客户询价客户报一个数字代理去数据库里找对应的汽车厂商。数据库里每一条记录包含三样东西厂商名字、某款车型的最低售价、最高售价。注意这里一个厂商对应一条记录每条记录本质上就是一个定价区间 [low, high]两个端点都算数。输入分成两层。第一层是所有厂商记录前面一个整数 D 表示记录数量后面 D 行每行是一个字符串加两个整数字符串是厂商名两个整数是 low 和 high。第二层是所有查询前面一个整数 Q 表示查询数量后面 Q 行每行一个整数 P代表客户报出的价格。有多组测试数据最前面还有一个 T 表示组数。输出逻辑也就三步。第一步在 D 条记录里数一数有多少个区间满足 low ≤ P ≤ high。第二步如果恰好只有一条记录命中输出那家厂商的名字。第三步如果一个都没命中或者命中了不止一条输出一个大写的 UNDETERMINED。整个过程和猜价格游戏很像你报一个价位数据库的专家判断这个价位到底属于哪家厂商判断不了的时候就直接告诉你不确定。这里有个容易让新手困惑的点题目名字里的 Expert Enough? 不是在问你要不要做多高明的决策恰恰相反它提醒你判定标准极其朴素——数命中个数。不找最便宜的不找区间最窄的不看厂商口碑纯粹数数。命中了恰好一条就回答否则就 UNDETERMINED。1.2 一个具体的例子帮你建立直觉用一组很小的自造数据走一遍流程比背十遍题目描述都管用。假设数据库里只有三条记录厂商名最低价最高价Apex1000015000Meridian2000030000Zed1200018000现在来三个查询。查询价格 12000三条记录里 Apex 命中10000 ≤ 12000 ≤ 15000Zed 也命中12000 ≤ 12000 ≤ 18000Meridian 不命中所以答案是 UNDETERMINED。查询价格 20000只有 Meridian 命中输出 Meridian。查询价格 9999三条都不命中输出 UNDETERMINED。看到没有关键就在那两张边界牌上。12000 同时落在两个区间里按常理说代理机构应该能猜中其中一个但题面规定重复命中就是不确定。这种反直觉的判定方式正是这道题想要训练的东西严格按规则执行不掺入任何现实常识。1.3 题源小考两个编号其实是同一题标题里的 UVA1237 和 LA4142 指的不是两道题而是同一道题在两个老牌题库里的对应编号。早期 AC 领域有很多题库同一道区域赛题目往往会在不同平台各挂一个号导致后来检索时经常看到两个编号并列出现。刷题时认准其中一个提交就行代码是同一份。搜索引擎里很多人把两个编号一起写本质上是在帮后来者定位这道题的多重身份。对新手来说这道题真正的价值在于规模小、结构简单非常适合练习读题 → 建模 → 暴力遍历 → 卡边界这一整套流程。别小看这套流程很多人打了好几年比赛最后翻车的仍然是边界和输出格式。2. 算法选型为什么迭代就是这道题的正解2.1 数据范围约束条件才是第一决策依据标题里特意带了个【迭代】说明解法的核心就是最朴素的遍历每条查询把所有厂商记录从头到尾扫一遍。有些同学一看到匹配查询两个字就条件反射想排序、想二分、想线段树。先按住这个冲动看看约束条件。老题面上数据库记录条数 D 和查询次数 Q 都在千量级以内测试数据组数也不大。就算按 D 1000、Q 1000 的极限来算一组数据最坏也就是一百万次整数比较。这个量级放在当年那些主频不到 1GHz 的评测机上都是瞬间完成的事放到现在更是连热身都算不上。同样是解决一个问题你花二十分钟写一个复杂的线段树和花三分钟写一个 for 循环运行时间都差不多甚至循环还更快那选哪个不言自明。算法竞赛里有一个经常被新手忽略的事实约束条件本身就是题面给你的最强提示。D 和 Q 都是三位数这就是在明说你随便扫。如果 D 和 Q 是 10^5 量级那才需要认真考虑扫描线或者更高级的数据结构。看到范围再动手是解题的第一原则。2.2 复杂度评估O(D×Q) 的真实开销用大 O 来表示这个解法的时间复杂度是 O(D×Q)空间复杂度 O(D)。推导过程很简单每组数据有 D 条记录每条查询都要完整遍历一遍所以单次查询是 O(D)Q 次查询合计就是 O(D×Q)。最坏情况下 D 和 Q 都取 1000得到 10^6 次比较再算上多组测试数据总量也就到 10^7 级别。10^7 次基本操作意味着什么主流评测系统通常认为一秒内跑完 10^7 到 10^8 次基本操作都在安全范围内。也就是说这份代码的实际耗时根本不在这十万百万次比较上而是在输入输出的系统调用上。你就算把所有比较全部换成更复杂的操作运行时间也不会有肉眼可见的变化。这种余量很重要。比赛中你永远要把不确定因素考虑进去评测机负载高不高、输入文件是不是特别大、其他选手是不是把评测队列堵满了。复杂度余量足够大你就不用担心这些外部因素专心保证逻辑正确就行。2.3 排序二分方案为什么不行重叠区间的问题有人会提方案把区间按左端点排序每次查询二分定位复杂度不就降到 O((DQ) log D) 了吗理论上听起来很美但实际操作会撞上一堵墙——区间可以重叠。你二分定位到左端点小于等于 P 的最大位置之后还得往前往后把所有覆盖 P 的区间都数出来而重叠区间可能扎堆出现。换句话说二分只帮你找到了第一个可能命中的位置但没法告诉你一共命中几个。举个例子就知道。区间 [1, 100]、[2, 99]、[3, 98]、[4, 97] 重叠得非常厉害查询 P 50 时这些区间全部命中。二分顶多帮你跳到第一条满足条件的记录后面到底还有多少条你仍然要往后扫。最坏情形下一次查询还是 O(D)。既然排序加二分在最坏情况下没有带来本质提升还引入了排序的额外复杂度和出错可能那它就不是一个好选择。真要严格加速得上区间差分配合扫描线或者面向点查询的线段树。代码量直接翻好几倍调试成本也跟着涨。而在 D 只有 1000 的约束下这些工作量毫无必要。过早优化是万恶之源这句话在竞赛里同样成立。3. 完整实现一份能直接 AC 的 C 代码3.1 数据存储结构体数组就够了既然要遍历记录就应该连续存放。C 语言里最直接的做法是定义结构体数组#include cstdio #include cstring struct Maker { char name[25]; int low; int high; } maker[1005];数组给到 1005 是在上限 1000 的基础上多留几个余量防止手滑越界。老评测机对越界行为非常敏感数组开大一点、循环边界写保守一点能省掉大量排查功夫。厂商名字最长不超过 20 个字符开 25 足够还给字符串结尾的\0留了位子。读入用scanf(%s%d%d, maker[i].name, maker[i].low, maker[i].high)就行因为题面保证厂商名字里没有空格。这点很关键如果名字里可能含空格你就得用别的方式读入但这题明确了是连续字符串所以%s是最省事的。有同学在这里非要用 getline反而给自己制造麻烦——scanf 读完整数后缓冲区里的换行符会留在原地下一行 getline 直接读到空串然后就是一连串莫名其妙的错位。3.2 查询核心逻辑cnt 和 idx 的分工每次查询的核心逻辑就一段循环int cnt 0, idx -1; for (int i 0; i D; i) { if (maker[i].low p p maker[i].high) { cnt; idx i; } } if (cnt 1) printf(%s\n, maker[idx].name); else printf(UNDETERMINED\n);cnt 负责计数idx 负责记住最后命中那条记录的下标。这两个变量为什么要分开因为 cnt 1 时idx 必然是唯一命中那条的下标cnt 超过 1 时idx 是什么已经无所谓反正输出 UNDETERMINED。判断逻辑集中在最后一行循环中间不用提前 break也不用记录多个下标代码意图一目了然。我特别强调 idx 要初始化成 -1。如果 D 条记录一条都没命中cnt 保持 0不会走到输出名字的分支idx 的初始值永远用不上。但万一你在别的题里复用这段逻辑忘了初始化 idx 又恰好走到输出名字分支那是未定义行为可能 RE 也可能输出乱码。每次进循环前重置 cnt 和 idx成本最低收益最大。判定条件写maker[i].low p p maker[i].high两个等号一个都不能少。这是闭区间的语义最低价和最高价本身都是有效价格。有人写成p maker[i].low p maker[i].high那等于把最高价挡在门外写成p maker[i].low p maker[i].high最低价和最高价全挡在门外。这类题 WA 十次有八次是挂在这种蠢问题上。3.3 完整代码与输出格式处理输出格式是老题库的另一大考点。这道题属于每组测试数据的输出之间要空一行的经典类型第一组数据的所有查询答案打完之后不能急着打第二组的第一个答案要先输出一个空行。空行多了会判 Presentation Error空行少了同样也会判错。我的写法是在整个 while(T--) 循环末尾补一个空行判断if (T) putchar(\n);T 减到 0 时说明这是最后一组数据不补空行否则每组数据结束后补一个。这个模式在很多老题里通用。需要提醒的是不同平台收录的版本对空行要求可能不完全一致万一你在某个平台上遇到 Presentation Error第一件事就是检查这里——把空行逻辑删掉试试很多时候就是版本差异。完整代码拼起来长这样#include cstdio #include cstring struct Maker { char name[25]; int low; int high; } maker[1005]; int main() { int T; scanf(%d, T); while (T--) { int D; scanf(%d, D); for (int i 0; i D; i) { scanf(%s%d%d, maker[i].name, maker[i].low, maker[i].high); } int Q; scanf(%d, Q); while (Q--) { int p; scanf(%d, p); int cnt 0, idx -1; for (int i 0; i D; i) { if (maker[i].low p p maker[i].high) { cnt; idx i; } } if (cnt 1) printf(%s\n, maker[idx].name); else printf(UNDETERMINED\n); } if (T) putchar(\n); } return 0; }这段代码在本地随便造几组数据测一下就能交。核心逻辑就这么多背下来都不亏。4. 踩坑实录WA 和 PE 都是怎么来的4.1 五大 WA 原因自查把常见错误整理成一张自查表提交之前逐条核对能省不少冤枉分症状原因解法边界价格全错判定写成开区间统一用 和 输出一直 UNDETERMINED厂商名字没读对读到空串别把 scanf 和 getline 混用只有最后一组对cnt 或 idx 忘记重置循环内初始化或每次查询前重置很奇怪的字符串错误UNDETERMINED 拼错这个单词按字节比对错一个字母就 WA数组越界或 RE数组开太小按上限加余量开到 1005UNDETERMINED 拼错这件事听起来很蠢但提交量真的大。常见错法有 UNdetermined、UNDETERMINED 多个 E、UNKNOW 混进来。OJ 的字符串比对是字节级的错一个字母就是 WA而且报错信息绝不会告诉你错在哪。另外老生常谈的一点价格相关变量统一用 int。这道题价格范围用 int 绰绰有余但如果你从别的区间题复制代码可能带进来奇怪的类型混用同样是潜在风险。4.2 Presentation Error空行那些事Presentation Error 在这类老题里几乎是必经之路。它和 WA 的区别在于你答案的内容是对的但格式和判题机期待的不一样。常见原因有三个。第一个就是组间空行。题面说两组输出之间要空一行你漏了PE。第二个是行尾空格。有些同学喜欢在字符串后面多打一个空格对齐判题机不会忽略它。第三个是最后一行是否有多余空行。代码里if (T) putchar(\n)的写法就是为了避免最后一组结束后再打一个空行。排查 PE 的思路很简单拿你的输出文件做十六进制查看看每一行的结尾到底是\n还是\r\n看两组之间到底空了几行。肉眼看不出来的差异十六进制全部现形。这个习惯一旦养成以后再遇到任何输出格式类题目都能少踩坑。4.3 本地自测数据与调试三步法提交前我习惯先在本地跑一组专门打边界的自造数据。价格恰好等于某条记录的 low 或 high确认命中构造全部命不中的查询确认输出 UNDETERMINED构造连续多条记录命中同一个价格确认输出 UNDETERMINED再构造 D 和 Q 都等于 1 的最小数据确认基本流程正常最后造一条 low 等于 high 的记录验证单点区间被正确处理。调试这类老题我用三步法。第一步样例输入喂进去比对样例输出。第二步边界数据对着程序逻辑一行行走查重点看 cnt 和 idx 在分支里的变化。第三步如果还是不对在循环里临时 printf 把每次命中的记录名打出来肉眼核对。大多数情况下这类题的 bug 根本用不到调试器纯靠肉眼和 printf 就能定位。真正要花时间的是弄清我哪里和题面不一致而不是我的代码哪里写错了。前者让你重新读题后者让你闷头调代码两种心态的产出完全不同。5. 延伸思考迭代之外的同类问题与工程启示5.1 从区间匹配问题看一类题型的共性Expert Enough? 本质上是一个静态区间集合上的包含查询问题给定一堆区间问一个点被哪些区间覆盖。这类问题在算法题里有一整个家族从最简单的暴力遍历到按端点排序加扫描线再到线段树、树状数组维护差分难度跨度非常大。我做过不少和它同源的题比如给定一堆人的上班时间段问某个时刻有多少人在岗比如给定一批优惠券的有效期问某天有多少张券可用。这些题题库不同、背景不同但抽象出来的模型惊人地一致区间加点查询。而每一道题到底该用多复杂的解法永远先看数据规模。小规模暴力中规模排序扫描大规模才轮到线段树。这道题的启蒙意义就在于当数据范围小的时候最朴素的做法就是正解。很多选手在训练中形成了一种肌肉记忆——看到查询就想预处理看到区间就想线段树。但其实开一个循环直接跑才是多数小数据题目里的最佳答案这种判断力比任何数据结构都金贵。5.2 迭代优先在工程里的现实价值放到真实工程里看先迭代、后优化同样是极其务实的策略。真实系统面对的很多数据集合量级并不大线性扫描往往比引入一棵复杂的索引树更可靠没有额外内存开销没有索引一致性问题没有过期缓存困扰出问题还好排查。性能问题要等数据量真正涨上来再解决而不是在一开始就搞一套重武器。所谓迎难而上之前先快速验证业务逻辑说的就是这个道理。我做过一个模拟项目处理一批每天几万条的交易记录当时有同事建议引入一套复杂的分区索引方案理由是想做高性能查询。结果简单迭代跑了三秒就出结果完全满足要求。后来数据量涨到了几十万级别才根据实测数据引入索引一步到位没有浪费半天功夫。所以这道题真正想教给我们的不是那个 for 循环本身而是一种判断力知道什么时候该用大炮什么时候该用匕首。我个人的体会是绝大多数性能问题都不是因为循环写得太朴素而是因为过早引入复杂的结构、把简单问题搞复杂了。先让正确的简单实现跑起来再拿数据说话去优化这条路走得最稳。刷完 Expert Enough? 之后我做区间类题目会先问自己一句这个规模真的需要上高级数据结构吗就这一句帮我少写了很多没必要的代码。