企业官网建设流程全解析

做算法题的人大概都见过这类题：题目不长，规则简单，但就是有无数人在一个不起眼的边界条件上翻车。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 一个具体的例子帮你建立直觉

用一组很小的自造数据走一遍流程，比背十遍题目描述都管用。假设数据库里只有三条记录：

现在来三个查询。查询价格 12000，三条记录里 Apex 命中（10000 ≤ 12000 ≤ 15000），Zed 也命中（12000 ≤ 12000 ≤ 18000），Meridian 不命中，所以答案是 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((D+Q) 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 拼错这件事听起来很蠢，但提交量真的大。常见错法有 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? 之后，我做区间类题目会先问自己一句：这个规模，真的需要上高级数据结构吗？就这一句，帮我少写了很多没必要的代码。