洛谷P4414 ABC题详解：排序+映射才是关键，避开WA陷阱

有些题名字越萌坑越深。P4414 ABC这种放在入门2的题单里看起来就是一道三分钟能写完的排序小题但我后来在讨论区见过不少WA记录也见过有人卡了一下午都没搞明白为什么我明明排好序了输出还是不对。问题的关键不在排序而在于三个字母和三个数之间的映射关系。这篇我就把P4414从题目拆解到三种写法再把我自己调试时踩过的坑和验证方法完整过一遍希望对正在入门刷题的你有点实际帮助。如果你能把这道题彻底吃透后面遇到结构类似但包装复杂的题目分析起来会轻快很多。文章不会太长但每一步我都尽量说明白为什么这么做。1. 这道题真正要练的不是排序而是三个数如何对上号1.1 题目在说什么三个整数配一张ABC牌先把题目翻译成人话。输入三个整数比如1 2 3再输入一个长度为3的字符串这个字符串由A、B、C三个大写字母组成。题目约定A代表三个数中最小的那个B代表中间那个C代表最大的那个。你要做的是按住这个字符串的顺序把对应的数输出出来。举个例子输入三个数是3 1 2字符串是CBA。因为C对应最大数3B对应中间数2A对应最小数1所以输出就是3 2 1。如果字符串是BAC输出就是2 1 3。这看起来简单但很多新手会下意识认为输入顺序就是ABC顺序直接把1 2 3原样输出那当然是错的。A、B、C这三个字母并不是输入变量的名字它们只是三个站位代号对应的是排序后第几小的位置。所以这道题的完整处理流程必须拆成两步第一步把三个数排序得到最小、中间、最大三个位置上的值第二步把字母当成查询规则从这三个位置里取数按字母串的顺序输出。两步缺一不可。1.2 排序只是手段藏在后面的映射关系才是核心为什么说排序不是重点因为如果题目只要求把三个数从小到大输出一个sort()就结束了根本不值得单独放进入门题单。P4414真正要练的是排序后的结果如何被一个外部规则重新组织并输出。这种思想放到真实开发里特别常见配置文件的key对应value状态机里的状态名对应具体数值数据库里的枚举字段对应id。你先把数据按某个维度整理好再用另一套索引规则去取。P4414就是这种先整理再索引逻辑的最小演示。我后来刷题养成了一个习惯拿到一道题先在纸上画三个框——输入是什么、中间状态是什么、输出是什么。数据从哪来到哪去画明白了再写代码。P4414这种题目虽然小却是练习这种拆解习惯的绝佳素材。你先想清楚排序和映射是两个阶段代码写起来几乎不会跑偏。2. 把题目要求和边界条件先钉死再谈怎么写代码2.1 输入输出到底长什么样题目输入走的是标准输入流。第一行是三个整数它们之间用空格或者换行隔开第二行是一个由A、B、C组成的字符串。在C里cin x y z s这种写法可以一口气把四样东西读完因为cin会自动跳过所有空白字符空格、换行、Tab。这是最省事的读法也是我推荐的做法。真正容易出问题的是getline的用法。如果你前面用了cin x y z紧接着用getline(cin, s)读字符串会读到一个空行——因为第一行输入结束后流里还残留一个换行符getline直接把它吃掉了。解决办法有两个要么全程用cin s要么在getline之前调用一次cin.ignore()把残留换行清掉。P4414本身用cin s就能避开这个坑但我还是想单独提出来因为这是入门阶段最经典的输入陷阱之一后面做需要读一整行带空格的字符串的题目时你一定会感谢现在记住了它。输出格式方面三个整数之间用一个空格隔开行末有没有多余空格评测系统通常不敏感。但比较稳的写法还是用一个循环控制空格输出不要在字符串后面无脑拼空格。养成规范输出的习惯对以后那些输出格式严格要求的题目只有好处。2.2 数据范围夹出来的边界负数、重复数字、极端值这题的数据范围我记得好像是-10000到10000也就是说三个数完全可能是负数。负数本身不影响排序用sort()处理就行但如果你自己想写比较逻辑比如用 if 判断谁大谁小就要特别小心别把负数的比较方向搞错。很多WA不是思路错是大于和小于写反了。比负数更隐蔽的是重复数字。比如输入5 5 8排序后是[5, 5, 8]那最小和中间位置都是5最大位置是8。如果字符串是ACB正确输出是5 8 5。排序法天然能处理重复数字因为相等时位置怎么换都一样但如果你用后面要讲的条件穷举法必须保证比较逻辑覆盖了x y、y z、x z这些情况否则很容易漏掉分支样例过了一提交就WA。极端值也不是问题只要你用的是排序而不是把最大值最小值硬编码进变量名这类奇怪做法。看到一道题先问自己三个问题数据范围多大有没有重复有没有负数这三个问题想清楚边界条件基本就锁死了。2.3 样例并不是摆设拿它做一遍纸面推演很多新手拿到样例之后瞄一眼就开始敲代码这是非常亏的。样例最大的价值是帮你验证你理解的题目逻辑对不对。拿样例来说如果输入是1 2 3字符串是ABC那输出自然是1 2 3如果字符串是CBA输出是3 2 1。我会建议你拿出笔在纸上先写出A最小1、B中间2、C最大3然后把这个映射代入字符串每一位查表写出结果最后再看官方给的样例输出是否一致。一致说明你理解对了不一致说明你一开始就理解偏了这时候改代码完全是白费力气回到题目重新读题才是最快路径。这个纸面推演的习惯是我觉得入门阶段最值得养成的好习惯之一。刷题到后面复杂题目里的数据结构越来越绕不先在纸上捋清楚直接开写几乎等于闭着眼走路。3. 三种解法逐个过一遍排序数组、条件穷举、映射表3.1 解法一排序后让字符当索引最推荐先给C写法这也是我推荐的首选方案#include bits/stdc.h using namespace std; int main() { int x[3]; string s; for (int i 0; i 3; i) cin x[i]; cin s; sort(x, x 3); for (int i 0; i 3; i) { if (i) cout ; cout x[s[i] - A]; } return 0; }这段代码的核心只有一行x[s[i] - A]。因为ASCII码里大写字母是连续的A、B、C的编码值依次相差1所以s[i] - A就能把字符转成0、1、2这三个下标正好对应排序后数组里的最小、中间、最大。B - A等于1C - A等于2这一步同时完成了字母到数字的映射是整个题目最值得品味的一句话。还有个小细节代码里sort(x, x 3)默认从小到大排排完之后x[0]是最小值x[2]是最大值。这个位置关系是固定的A一定查x[0]B一定查x[1]C一定查x[2]。所以整个程序本质上就是排序一次查询三次思路非常干净。3.2 解法二把六种排列直接穷举出来如果你还没学过排序函数或者做题时脑子里没想起排序也可以用条件判断硬写。思路是先求出三个数的最小值、中间值、最大值然后根据字符串内容分六种情况输出int a, b, c; cin a b c; string s; cin s; int mn min({a, b, c}); int mx max({a, b, c}); int mid a b c - mn - mx; if (s ABC) cout mn mid mx endl; else if (s ACB) cout mn mx mid endl; else if (s BAC) cout mid mn mx endl; // 后面还有 BCA、CAB、CBA 三个分支这种写法逻辑上没有问题代码也能过但缺点很明显分支多、代码重复、容易漏。反正就只有六种排列把六种都写全也没多难但我见过不少初学者只写了三四种样例刚好落在写过的分支里就AC了一提交就WA在没写的分支上。还有一个隐患是求mid的公式a b c - mn - mx在a、b、c是int且重复数字时也成立因为三个数之和减去最大最小剩下的自然就是中间值逻辑上没问题。我个人的建议是如果刚入门想练逻辑可以写一次穷举法作为思维训练如果想让代码简洁通用、以后还能复用那就掌握排序法。穷举法的价值在于帮你理清A、B、C 分别是什么但缺点在于无法推广到四个字母、五个字母的场景。3.3 解法三用dict/哈希做映射代码少但要有基础如果你用Python这道题可以写得很短核心思想是显式建一张映射表nums sorted(map(int, input().split())) s input().strip() mp {A: nums[0], B: nums[1], C: nums[2]} print(mp[s[0]], mp[s[1]], mp[s[2]])这段代码的思路非常直白排序之后nums[0]是最小值nums[1]是中间值nums[2]是最大值。然后建一个字典mp把A、B、C分别映射到这三个数上。最后用字符串的每一位去查表按顺序输出。相比C里用ASCII偏移的做法Python的字典更直观也更接近映射这个词的本义。C也可以用mapchar, int做同样的事但三个键的情况下数组加s[i] - A的写法已经完全够用没必要额外引入容器。这里想强调一个观点C和Python写这道题的差异根源不在语言本身而在于你是否理解字母到值本质上就是一次查找。理解了这一点换语言写只是语法层面的小事。3.4 三种写法横向对比从代码量、出错率、可读性看三种方案放在一起比较差别就清楚了方案代码量核心思想主要出错点适用场景排序 字符索引短排序后用ASCII偏移做下标忘记s[i] - A直接拿字符当下标推荐所有人掌握可推广到同类题条件穷举中等显式枚举六种排列顺序分支容易漏比较条件易写反适合练逻辑但不利于复用dict / 哈希映射很短显式建字母到数值的映射表不熟字典语法时不好调试Python选手、追求最直观可读性如果你刚开始刷题我建议优先掌握第一种。它同时覆盖了排序和映射两个考点代码又短以后遇到按指定顺序重排数组这类题目几乎可以把思路平移过去用。4. 我实际调试中踩过的坑比较方向写反、字符索引没减A4.1 坑一从小到大写成从大到小输出全反我第一次写这题的时候为了显得自己不用现成的sort手写了一个选择排序结果比较条件写反了把从小到大排写成了从大到小排。输入1 2 3和字符串ABC期望输出1 2 3实际输出却是3 2 1。更气人的是我当时还以为问题出在字符串处理上盯着s[i]看了半天完全没往排序方向想。后来我学会了一个特别基础的调试手段打印中间结果。在排序代码后面加一行cout x[0] x[1] x[2] endl;看看排完序之后数组到底是什么顺序。这一打印就现出原形了——数组是[3, 2, 1]问题根本不在字母映射而在排序方向。从那时起我就养成了习惯任何排序相关的题目AC之前先确认中间数组的顺序符合预期。不要把输出结果不对直接归因到最显眼的那段代码上先验证数据状态再下结论。4.2 坑二拿着字符A直接当数组下标这个坑我也是在C里真实踩过的。把代码写成x[s[i]]编译居然不报错但运行的时候C的ASCII码是67数组直接越界访问输出是一个莫名其妙的巨大负数在OJ上就是那种让你完全摸不着头脑的WA或者RE。为什么我会写错因为如果你先接触Pythons[i]可以直接当字典的key用自然觉得字符就是索引。但在C里字符在表达式里会被当成整数参与运算A就是65它不会自动变成0。正确写法永远是s[i] - A把ASCII码转成从0开始的偏移量。这个字符转索引字符减A的套路我在后面的刷题里反复用到统计字母出现次数、处理二维字符矩阵、做字母排序……遇到的次数多了它已经成了我脑子里的默认操作。建议你也把它单独记成一条笔记不需要思考见到大写字母要当下标就条件反射地减掉A。这个习惯能帮你省下一堆莫名其妙的RE。4.3 坑三读入字符串时被多余空格坑到再讲一个输入上的坑这个坑尤其容易出现在换题刷的时候。假设你之前写过别的题用了cin a b c这题你也照常读前三个数但第二行字符串你选了getline(cin, s)来读。这时候第一行输入结束后流里还留着一个换行符getline会直接把这个空行读走s就变成了空字符串遍历输出时什么都打印不出来。解决方式我前面提过要么全程用cin s让它自动跳过换行要么在getline之前调用cin.ignore()清掉残留字符。P4414这道题用cin s是最干净的因为字符串本身不含空格cin s完全能读对。但如果你在别的题目里遇到需要读一整行含空格的字符串那getline和ignore的配合就必须熟练。我现在刷题的习惯是先判断一行里有没有空格有空格才用getline否则一律cin 。4.4 验证技巧一组能打的随机测试数据写完代码别急着提交先自己造几组数据跑一遍。我给出的测试集是这样的升序数据1 2 3ABC期望输出1 2 3降序数据3 2 1CBA期望输出3 2 1乱序数据100 -5 3BAC期望输出3 -5 100重复数据5 5 8ACB期望输出5 8 5负数极端-10000 0 10000CAB期望输出10000 -10000 0这五组数据覆盖了升序、降序、乱序、重复、负数五种基本情况。如果代码全部输出正确再提交就会踏实很多。这个造数据—跑程序—核对输出的闭环越早养成越好。很多新手是写完之后直接交WA了再回来查一来一回浪费大量时间而且没有中间过程可以复盘。自己先测一遍至少能过滤掉一半的低级错误。5. 从这道入门题辐射出去给算法新手的几句实在话5.1 刷题最该练的是把题目翻译成逻辑我敲代码之前一定先把题目口译一遍读三个数排序按字符串映射输出。就这三步翻译完再动手实现不过是体力活。很多人在入门阶段卡住问题不出在语法而是看懂了题目但不知道怎么变成代码。我一直觉得最好的练习不是狂刷题而是逼自己把题目拆解成步骤。每AC一道题就在草稿纸上把过程写一遍输入是什么、要做什么处理、输出是什么。一开始可能觉得麻烦但坚持十几道题之后面对新题脑子里会自动浮现出处理流程。P4414就是最适合拿来练这个流程的小题因为步骤少拆解起来没有压力。5.2 造数据的习惯比背模板值钱我见过一些同学碰到题目先看题解把模板背下来然后换一道类似的题又做不出来。问题出在只会套模板不会验证代码。模板是别人的思考结果你没有参与它的推导过程自然不知道它的适用范围和边界在哪。我的土办法是每道题AC之后故意把代码改坏一两处比如把s[i] - A改成s[i]或者把sort的比较方向改反再跑一遍测试数据观察输出变化。这样做的好处是你会非常直观地看到哪段代码负责什么逻辑下次写错了一眼就能定位。代码越短的题越适合做这种破坏实验P4414几乎是完美的实验对象。5.3 同思路的题可以往哪些方向找P4414表面上是一道排序题实际上练的是索引映射。这个思路在后面的题目里会反复出现比如给你一个数组和一个排列顺序数组让你按顺序重新排列元素比如字母和数字之间的互相映射最典型的是统计一串大写字母里每个字母出现了多少次这时候c - A当下标的方法可以直接套用再比如进制转换类题目字符0到9、A到F和数值之间的转换本质上也是映射。如果你刷题时看到给一个字符串按指定顺序输出用数组统计字母频次这类描述第一反应就可以想一想能不能用排序或整理 字符减A做索引这套老办法解决。题目包装千变万化底层逻辑相通这就是拆解和归纳的价值。做完P4414之后我给自己写了一句总结题目短、难度低不代表没含金量。这道题教会我的不是sort怎么用而是排序和映射是两个独立阶段分析问题时要分开想。后来遇到更复杂的题这种拆解习惯帮我少走了很多弯路。如果你也正处在入门期建议别急着看题解先按我上面说的方法在纸上推演一遍再用三种写法各写一遍收获会比随手AC大得多。