1. 项目概述从一道PTA天梯赛真题说起最近在带学生刷PTA程序设计类实验辅助教学平台的天梯赛题目L1-027 “出租”这道题出现的频率相当高。乍一看题目描述像是要处理一个电话号码的映射问题很多新手会下意识地想到用map或者set这类高级数据结构。但仔细读完题目要求和样例你会发现这道题的核心考点其实非常“朴实”——它考察的是对数组、字符串的基本操作能力以及一种被称为“暴力枚举”或“模拟”的解题思想。用C的STL当然可以优雅地解决但题目本身更鼓励甚至可以说是为“暴力实现”量身定做的。所谓“暴力”在这里并非指代码粗糙而是指一种直接、不取巧、按部就班模拟题目描述过程的方法。这种方法虽然时间复杂度可能不是最优但对于数据规模明确的竞赛题尤其是L1级别它往往是思路最清晰、最不容易出错、也最锻炼基本功的解法。今天我就结合这道题详细拆解一下如何用C进行“暴力实现”并分享其中涉及的关键技巧和常见“坑点”。2. 题目核心需求与逻辑拆解2.1 问题描述还原首先我们得彻底理解题目要我们做什么。题目“出租”的背景是这样的我们需要处理一个11位的手机号码字符串。例如给定号码13505711862。我们需要完成两个主要任务找出号码中所有不同的数字并按从大到小的顺序排列。以上述号码为例出现的数字有1, 3, 5, 0, 7, 8, 6, 2。去重后从大到小排序得到序列8, 7, 6, 5, 3, 2, 1, 0。这个序列将被视为一个“索引表”或“座位号”列表。根据这个排序后的数字序列生成原电话号码每个数字在该序列中的位置索引。这里有一个关键细节索引是从0开始的。也就是说我们要为原号码13505711862的每一位找到它在{8,7,6,5,3,2,1,0}这个列表中的下标。数字1在列表中的下标是6列表第7个位置索引从0开始。数字3的下标是4。数字5的下标是3。... 以此类推。 最终我们会得到一个新的索引序列int[] arr {1, 3, 5, 0, 5, 7, 1, 1, 8, 6, 2}对应的索引序列是{6, 4, 3, 7, 3, 1, 6, 6, 0, 2, 5}。输出格式要求先输出排序后的数字序列以逗号空格分隔再输出索引序列同样以逗号空格分隔且格式为int[] arr new int[]{...};。2.2 “暴力实现”的思维定位为什么说这道题适合“暴力实现”因为它的步骤非常线性且数据规模极小一个固定11位的字符串。我们不需要复杂的算法优化只需要老老实实地分步完成步骤一遍历字符串识别出所有出现过的数字字符。步骤二将这些数字去重。步骤三将去重后的数字进行排序从大到小。步骤四再次遍历原字符串为每一位数字在排序后的列表中查找其位置。这里的“暴力”主要体现在步骤四的“查找”操作上。我们完全可以遍历排序后的列表来匹配当前数字从而找到其索引。对于一个最大长度为10的列表和一个长度为11的字符串这种查找的代价O(n*m)完全可以接受这就是暴力查找。与之相对的“非暴力”解法可能会使用哈希表unordered_map来存储数字到索引的映射将查找时间降到O(1)但代码结构会稍有不同。注意很多同学在这里会混淆“去重”和“排序”的顺序。必须先收集所有数字再去重最后排序。如果边收集边排序并试图去重逻辑会变得复杂容易出错。3. 暴力实现的核心代码解析接下来我们一步步用C代码实现上述逻辑。我会使用最基础的数组和循环结构尽量避开高级STL容器以体现“暴力”和“基础”的特点。3.1 数据结构选择与输入处理首先我们需要存储原始号码、出现的数字以及最终的索引。#include iostream #include string using namespace std; int main() { string phone; // 存储11位手机号码 cin phone; // 用于标记数字0-9是否出现过 bool digit_appeared[10] {false}; // 用于存放去重后并排序的数字 int unique_digits[10]; int unique_count 0; // 用于存放最终索引结果 int index_result[11]; }这里digit_appeared是一个布尔数组下标0-9对应数字0-9。这是一个非常经典的“桶”思想用于高效去重。unique_digits数组用于存放最终排序后的不同数字unique_count记录其数量。index_result用于存放原号码每一位对应的索引。3.2 步骤一与步骤二遍历、识别与去重我们遍历电话号码字符串将字符转换为数字并标记其出现过。// 步骤1 2: 识别并去重 for (int i 0; i 11; i) { int digit phone[i] - 0; // 将字符0-9转换为整数0-9 if (!digit_appeared[digit]) { digit_appeared[digit] true; } }这段代码结束后digit_appeared数组中值为true的位置对应的数字就是在号码中出现过的。3.3 步骤三构建从大到小的排序序列现在我们需要根据digit_appeared数组生成一个从大到小排序的unique_digits数组。由于数字范围只有0-9我们可以采用一种更“暴力”但清晰的方法直接从9到0遍历如果该数字出现过就加入数组。// 步骤3: 构建从大到小的排序序列 for (int digit 9; digit 0; --digit) { if (digit_appeared[digit]) { unique_digits[unique_count] digit; unique_count; } }这种方法巧妙地利用了下标顺序直接得到了从大到小排序的结果省去了显式调用排序函数的步骤是这道题的一个小技巧。3.4 步骤四暴力查找生成索引序列这是“暴力”二字体现最明显的地方。对于原号码的每一位数字我们遍历unique_digits数组直到找到匹配项记录其下标。// 步骤4: 为原号码每一位查找索引 for (int i 0; i 11; i) { int current_digit phone[i] - 0; for (int j 0; j unique_count; j) { if (unique_digits[j] current_digit) { index_result[i] j; break; // 找到后立即跳出内层循环 } } }这里的内层for循环就是一次线性查找对于每个数字最坏情况下需要遍历整个unique_digits数组长度10。3.5 格式化输出最后按照题目要求的格式进行输出。输出需要注意逗号后的空格以及最后没有逗号和空格。// 输出排序后的数字序列 cout int[] arr new int[]{; for (int i 0; i unique_count; i) { if (i ! 0) cout , ; cout unique_digits[i]; } cout }; endl; // 输出索引序列 cout int[] index new int[]{; for (int i 0; i 11; i) { if (i ! 0) cout , ; cout index_result[i]; } cout }; endl;4. 完整代码与逐行注释将以上所有部分组合起来并加上详细注释就得到了完整的“暴力实现”代码。#include iostream #include string using namespace std; int main() { // 1. 读入电话号码字符串 string phone; cin phone; // 2. 初始化辅助数组 bool appeared[10] {false}; // 标记数字0-9是否出现 int sorted_digits[10]; // 存放从大到小排序的不同数字 int sorted_cnt 0; // 排序数字的实际个数 int index[11]; // 存放最终索引结果 // 3. 第一遍遍历标记出现过的数字实现去重 for (int i 0; i 11; i) { int num phone[i] - 0; // 字符转整数 appeared[num] true; // 标记为已出现 } // 4. 第二遍遍历从9到0生成从大到小的排序序列 for (int num 9; num 0; --num) { if (appeared[num]) { // 如果该数字出现过 sorted_digits[sorted_cnt] num; // 加入排序数组 sorted_cnt; // 计数增加 } } // 此时sorted_digits[0]~sorted_digits[sorted_cnt-1] 就是从大到小排列的不同数字 // 5. 第三遍遍历原号码为每一位查找在排序序列中的索引 for (int i 0; i 11; i) { int current_num phone[i] - 0; // 暴力查找遍历排序数组寻找匹配项 for (int j 0; j sorted_cnt; j) { if (sorted_digits[j] current_num) { index[i] j; // 记录索引从0开始 break; // 找到后立即跳出提高效率 } } } // 6. 格式化输出第一部分排序后的数字序列 cout int[] arr new int[]{; for (int i 0; i sorted_cnt; i) { if (i ! 0) cout , ; cout sorted_digits[i]; } cout }; endl; // 7. 格式化输出第二部分索引序列 cout int[] index new int[]{; for (int i 0; i 11; i) { if (i ! 0) cout , ; cout index[i]; } cout }; endl; return 0; }5. 常见问题与实战调试技巧即使思路清晰在实现过程中尤其是竞赛环境下还是会遇到一些典型问题。下面是我总结的几个高频“坑点”和解决技巧。5.1 数组越界与初始化问题问题appeared数组大小为10对应下标0-9。如果转换数字时出错或者访问phone字符串越界比如假设它不是11位会导致未定义行为。排查在读取phone后可以加一句断言或判断if (phone.length() ! 11) { /* 处理错误 */ }。虽然题目保证输入正确但自己代码的健壮性很重要。确保phone[i] - 0的结果一定在0-9之间。对于合规输入这没问题。技巧在本地调试时可以使用cout (int)phone[i] endl;来查看字符的ASCII码确认减0操作是否正确。5.2 输出格式错误这是PTA判题系统最常见的失分原因之一。格式必须严格匹配包括空格、逗号、分号、花括号。坑点1逗号与空格。题目示例是int[] arr new int[]{8, 7, 6, 5, 3, 2, 1, 0};注意,后面有一个空格。很多同学输出时忘了这个空格。坑点2末尾符号。序列输出最后是};而不是, };。在循环输出时通常用if (i ! 0) cout “, “;来控制这样第一个元素前不加逗号最后一个元素后也不会有多余的逗号。自查方法将你的程序输出和题目样例输出复制到文本比较工具或直接目测进行逐字符对比这是最有效的方法。5.3 去重与排序的逻辑混淆错误示范试图在遍历原号码时边遍历边将数字插入到一个“有序且去重”的数组中。这需要维护数组有序且唯一逻辑复杂容易写错。正确思路严格遵循“收集 - 去重 - 排序”的三段式管道操作。本例中“收集”和“去重”通过布尔数组一次性完成“排序”通过从9到0遍历取巧完成。逻辑分离清晰易懂。5.4 索引查找的优化思考虽然我们用了暴力查找但可以思考一下如何优化。既然我们已经有了从大到小排序的数字列表sorted_digits并且数字范围是0-9我们可以预计算一个映射表将数字直接映射到其索引。// 在生成sorted_digits后构建映射表 int digit_to_index[10]; // 数字到索引的映射 for (int i 0; i sorted_cnt; i) { digit_to_index[sorted_digits[i]] i; } // 然后生成index数组时就可以直接查表O(1)复杂度 for (int i 0; i 11; i) { index[i] digit_to_index[phone[i] - 0]; }这种方法在查找步骤上更高效代码也更简洁。它依然属于“模拟”或“直接实现”的范畴但使用了更高效的数据结构一个小的查找表。这提醒我们“暴力”不等于“笨拙”在明确数据范围的情况下用空间换时间是非常实用的策略。5.5 使用STL的“优雅暴力”版本为了对比这里给出一个使用C STL中vector、set和find函数的版本。它本质上还是模拟过程但利用了现成的轮子。#include iostream #include string #include set #include vector #include algorithm using namespace std; int main() { string phone; cin phone; setint, greaterint digit_set; // 从大到小排序的集合 for (char c : phone) { digit_set.insert(c - 0); } vectorint sorted_digits(digit_set.begin(), digit_set.end()); // 注意set默认升序我们用了greaterint使其降序 vectorint index; for (char c : phone) { int num c - 0; // 使用find进行查找依然是线性查找但代码简洁 auto it find(sorted_digits.begin(), sorted_digits.end(), num); index.push_back(distance(sorted_digits.begin(), it)); } // 输出部分略格式同上 // ... }这个版本更短但需要理解set、vector、find和distance的用法。在竞赛中两种写法都可以基础版本更能体现算法本质STL版本则书写更快。对于初学者我强烈建议先从基础数组版本掌握起再学习STL版本这样才能真正理解底层在发生什么。6. 从本题延伸的编程思维训练L1-027 “出租”虽然简单但它是一个绝佳的训练模型涵盖了几个非常重要的编程思维问题分解与步骤化将复杂问题拆解成几个明确的、顺序执行的子任务输入-去重-排序-映射-输出。这是解决任何编程问题的第一步。数据表示与转换如何用程序中的数据结构数组、字符串来表示现实问题中的概念电话号码、数字列表、索引。特别是字符数字‘5’到整数5的转换- ‘0’是基础中的基础。查找与映射核心是建立从一个集合数字到另一个集合索引的对应关系。暴力查找是最直观的方法构建映射表如digit_to_index是更高效的方法这引入了“空间换时间”的思想。边界条件与格式化输出处理最后一个元素不加逗号、严格匹配空格等细节是编程严谨性的体现。在自动化判题系统中格式错误和结果错误同等严重。在实际教学中我发现很多同学卡住不是因为算法多难而是卡在“字符减‘0’忘了”、“数组下标搞错”、“输出格式不对”这些非常基础的细节上。这道题就像一面镜子能很好地反映出一个程序员的基本功是否扎实。把这道题吃透其价值远不止于通过一道PTA题目而是为处理更复杂的字符串和数组问题打下坚实的基础。下次当你遇到一个看似复杂的问题时不妨试试这种“暴力”的、一步一步模拟的方法它往往能帮你理清思路找到突破口。