C++ STL map与vector实战：华为OD机试分组统计与排序题解

1. 项目概述一道典型的华为OD排序与数据处理题最近在准备华为OD机试的朋友应该对“统计射击比赛成绩”这道题不陌生。它频繁出现在各类真题回忆录和备考资料里是检验候选人基础数据结构应用和逻辑严谨性的经典题目。题目本身描述很清晰给你一堆杂乱无章的射击记录每条记录包含选手ID和本次射击的分数你需要为每位选手计算其最高的三个分数之和然后根据这个“总成绩”进行排名。听起来简单但里面藏着几个容易踩坑的细节比如选手成绩少于3个要直接忽略总分相同时要按ID降序排列。这正是华为OD机试题的特点——问题本身不难理解但要求你在实现时对边界条件和排序规则有精准的把握。这道题非常适合用C来解。C的STL容器特别是map和vector在处理这种“按ID分组统计”的问题时非常得心应手。同时自定义排序规则也是C面试和机试中的高频考点。通过这道题我们不仅能复习map的用法、vector的排序还能深入理解如何组织数据、设计算法流程以及如何写出清晰、健壮的代码。对于正在刷题备战机试或者想巩固C基础编程能力的朋友来说这是一个很好的练手项目。接下来我会带你从零开始一步步拆解思路并用C实现一个高效、易读的解决方案。2. 核心思路与数据结构选型面对这个问题我们首先要理清数据处理流程。输入是三行射击次数N、N个ID序列、N个分数序列。输出是一个按规则排序后的ID序列。核心任务可以分解为三步数据收集、成绩计算、排序输出。为什么选择std::mapint, std::vectorint作为核心数据结构这是本题的关键决策。我们需要为每个选手存储他所有的射击成绩。选手ID是整数并且范围给定0-99我们可以用数组但使用std::map更具通用性和清晰性。map的键Key是选手ID值Value是一个vectorint用来动态存储该选手的所有分数。这样当我们遍历输入数据时就可以很方便地将分数push_back到对应ID的vector中。即使某个ID第一次出现map也会自动创建该键值对其对应的vector初始为空这省去了我们手动判断和初始化的麻烦。计算逻辑的细化数据收集与分组同步遍历ID数组和分数数组将分数插入到map[ID]对应的vector中。筛选与计算遍历map中的每一个键值对即每一位选手首先检查该选手的成绩数量即vector的size()是否大于等于3。如果小于3直接跳过该选手。如果成绩数量足够则对该选手的所有成绩进行降序排序使用std::sort配合std::greaterint()。然后取排序后的前三个元素即最高的三个分数求和。排序与输出计算完所有合格选手的总分后我们需要根据总分进行排名。这里不能直接对map排序因为map本身是按Key排序的。我们需要将数据转移到另一个容器中进行排序。通常我们会创建一个vectorpairint, int其中每个元素是(选手ID, 最高三成绩之和)。然后对这个vector使用std::sort并传入一个自定义的比较函数或lambda表达式来实现“总分降序总分相同时ID降序”的复杂规则。关于排序规则的设计思考这是本题的另一个易错点。简单的总分降序很容易写但加上“同分时ID降序”这个条件就需要我们仔细设计比较逻辑。在自定义比较函数中我们通常返回一个布尔值表示第一个参数是否应该排在第二个参数之前。对于本题规则是优先比较总分如果a的总分 b的总分那么a应该排在b前面返回true。如果总分相等则比较ID如果a的ID b的ID那么a应该排在b前面返回true。其他所有情况返回false。 这个逻辑用代码实现时务必清晰否则会导致排序结果错误。3. 代码实现与逐行解析理清了思路我们来看具体的C实现。我会提供完整的代码并对其中的关键部分进行详细注释。#include iostream #include vector #include map #include algorithm #include sstream using namespace std; int main() { int N; cin N; // 读取射击总次数 cin.ignore(); // 忽略换行符为后续getline做准备 // 读取ID序列和分数序列 string idLine, scoreLine; getline(cin, idLine); getline(cin, scoreLine); // 使用字符串流解析逗号分隔的字符串 stringstream idStream(idLine); stringstream scoreStream(scoreLine); vectorint ids(N); vectorint scores(N); for (int i 0; i N; i) { char comma; // 用于读取逗号 idStream ids[i]; if (i N - 1) idStream comma; // 读取并丢弃逗号最后一个数字后没有逗号 scoreStream scores[i]; if (i N - 1) scoreStream comma; } // 核心数据结构map选手ID, 该选手所有成绩列表 mapint, vectorint playerScores; // 第一步数据分组将成绩按选手ID归类 for (int i 0; i N; i) { int playerId ids[i]; int score scores[i]; playerScores[playerId].push_back(score); } // 第二步计算每位选手的最高三个成绩之和并收集合格选手的信息 vectorpairint, int validPlayers; // 存储选手ID, 最高三成绩之和 for (const auto entry : playerScores) { int playerId entry.first; const vectorint scoreList entry.second; // 规则2成绩少于3个忽略该选手 if (scoreList.size() 3) { continue; } // 复制一份成绩列表进行排序避免修改原数据虽然这里修改了也不影响后续但是个好习惯 vectorint sortedScores scoreList; // 降序排序以便取前三个最高分 sort(sortedScores.begin(), sortedScores.end(), greaterint()); // 计算最高三个成绩之和 int topThreeSum 0; // 注意这里使用min(3, sortedScores.size())是更安全的写法虽然我们已经判断过size3 for (int i 0; i 3 i sortedScores.size(); i) { topThreeSum sortedScores[i]; } // 将合格选手及其总分存入容器 validPlayers.push_back({playerId, topThreeSum}); } // 第三步对合格选手进行排序 // 使用lambda表达式定义复杂的排序规则 sort(validPlayers.begin(), validPlayers.end(), [](const pairint, int a, const pairint, int b) { // 规则1按总分降序 if (a.second ! b.second) { return a.second b.second; // 总分高的排前面 } // 规则3总分相等时按ID降序 return a.first b.first; // ID大的排前面 }); // 第四步输出结果 for (int i 0; i validPlayers.size(); i) { cout validPlayers[i].first; if (i ! validPlayers.size() - 1) { cout ,; } } cout endl; return 0; }关键代码段解析输入处理getline(cin, idLine); getline(cin, scoreLine);使用getline读取整行因为输入是以逗号分隔的字符串。然后使用stringstream配合循环来解析每个整数这是处理这类格式输入的常用且稳健的方法。数据分组playerScores[playerId].push_back(score);这行代码是map妙用的体现。无论playerId是否已在map中playerScores[playerId]都会返回一个vectorint的引用如果不存在则自动插入一个空vector然后我们直接向这个vector中添加分数即可。成绩计算与筛选if (scoreList.size() 3) { continue; }这里严格执行了题目规则2。注意我们是在遍历map时进行判断的这意味着成绩少于3个的选手根本不会进入后续的validPlayers列表。自定义排序规则Lambda表达式[](const pairint, int a, const pairint, int b) { if (a.second ! b.second) { return a.second b.second; } return a.first b.first; }这是整个排序逻辑的核心。Lambda表达式清晰表达了我们的排序优先级首先比较第二个元素second即总分降序如果相等再比较第一个元素first即选手ID也是降序。这个比较函数决定了sort算法如何排列元素。输出格式控制if (i ! validPlayers.size() - 1) { cout ,; }这是一个常见的技巧用于在输出序列元素时只在元素之间打印分隔符如逗号避免在最后一个元素后多打印一个逗号从而严格符合题目输出格式要求。4. 算法复杂度分析与优化探讨完成基本实现后我们有必要分析一下代码的效率并看看是否有优化空间。这对于机试中应对更大数据量的场景或者理解算法本质都很有帮助。时间复杂度分析假设总射击次数为N共有M位不同的选手。数据读取与解析O(N)这是必须的。数据分组遍历N次每次在map中查找或插入是O(log M)所以这部分是O(N log M)。由于M最大为100ID范围0-99log M很小近乎常数。成绩计算遍历M位选手。对于每位选手假设他有K个成绩平均K N/M。复制成绩列表O(K)排序成绩列表O(K log K)。使用std::sort平均复杂度为O(K log K)。计算前三名和O(1) 所以这部分总复杂度约为 O(M * (K K log K)) O(N N log (N/M))。在最坏情况下成绩极度集中于少数选手K会很大但题目限制了N100所以完全可接受。最终排序对validPlayers最多M个元素排序复杂度为O(M log M)。综合来看整个算法的时间复杂度主要由对每位选手的成绩列表进行排序这部分主导即O(N log K)级别。在N100的约束下这个复杂度是瞬间完成的。空间复杂度分析我们主要存储了playerScores(map): 存储了所有N个成绩O(N)。validPlayers(vector): 最多存储M个元素O(M)。在计算过程中为每位选手复制了一份成绩列表用于排序这带来了额外的O(K)临时空间但每个选手处理完后即释放。 总空间复杂度为O(N)。潜在的优化点虽然对于本题规模无需优化但我们可以思考一下如果数据量变大比如N上万如何改进避免全排序我们只需要每个选手的前三大分数而不需要整个有序列表。因此可以使用一个大小为3的最小堆Min-Heap来维护当前遇到的最高三个分数。遍历一个选手的所有成绩时将分数放入堆中如果堆大小超过3则弹出最小的那个。这样处理K个成绩的时间复杂度可以从O(K log K)降低到O(K log 3)即近似O(K)。C中可以用priority_queueint, vectorint, greaterint来实现最小堆。输入优化如果输入格式固定可以使用更快的自定义解析函数来替代stringstream但提升微乎其微。容器选择由于选手ID范围固定且很小0-99我们可以直接用大小为100的数组vectorint scores[100]来代替map将查找复杂度从O(log M)降为O(1)。这在知道ID范围且范围不大时是更高效的选择。注意在华为OD机试或大多数编程竞赛中正确性和代码清晰度是第一位的在时间复杂度满足要求的前提下不必追求极致的微优化。使用map和sort的版本逻辑清晰易于理解和调试是更推荐的做法。只有在明确遇到性能瓶颈时才考虑上述优化。5. 常见错误与调试技巧在实际编写和调试这道题时我遇到过也见过别人遇到一些典型的错误。这里总结一下帮你避坑。1. 输入格式处理错误这是新手最容易出错的地方。题目输入是三行第二、三行是逗号分隔的字符串。错误做法直接用cin 逐个读取整数但遇到逗号会失败。正确做法如我们代码所示先用getline读入整行字符串再用stringstream解析。或者也可以使用cin.get()判断下一个字符是否是逗号并跳过但stringstream的方法更通用、更清晰。2. 排序规则实现错误自定义排序规则是本题的核心也是易错点。错误示例1逻辑反了// 意图总分降序同分时ID降序 if (a.second b.second) return true; if (a.first b.first) return true; // 错误只要ID大的就返回true忽略了总分不同的情况 return false;这个比较函数没有正确处理总分优先的原则。如果a总分小于b总分但a的ID大于b的ID它也会返回true导致排序错误。错误示例2未严格降序if (a.second ! b.second) { return a.second b.second; } // 总分相等时错误地按ID升序排列了 return a.first b.first; // 题目要求ID降序这是升序调试技巧对于自定义排序最好在写完lambda后用几组简单的测试数据在脑子里或纸上模拟一下排序过程特别是边界情况如总分相等、ID大小关系等。3. 忽略“成绩少于3个”的规则在遍历map计算总分时忘记检查vector的size()是否大于等于3导致将无效选手也纳入了排名。务必在计算前先进行判断。4. 输出格式错误题目要求输出ID序列以逗号分隔且末尾无逗号和无空格。常见错误在循环中直接cout id “,”;这样会在最后一个ID后面也输出一个逗号。我们的做法判断是否是最后一个元素如果不是才输出逗号。这是一种清晰的方法。也可以先输出第一个ID然后循环输出“,” id。5. 容器选择不当有人可能会尝试用unordered_map代替map。unordered_map的查找是O(1)似乎更快。但需要注意的是unordered_map的遍历顺序是不确定的。虽然在本题中我们后续会对validPlayers进行排序初始顺序不影响结果但使用map可以使我们分组后的数据按ID有序在调试时观察中间结果更直观。在性能差异可忽略的情况下map的确定性更有优势。调试与测试建议使用题目给的示例首先用示例输入13、3,3,7,4,4,4,4,7,7,3,5,5,5、53,80,68,24,39,76,66,16,100,55,53,80,55测试确保输出是5,3,7,4。构造边界测试用例所有选手成绩都少于3个输入4、1,2,1,2、10,20,30,40。预期输出应为空或什么都不输出。有选手成绩刚好3个输入3、1,1,1、100,90,80。输出1。总分大量相同输入6、1,1,1,2,2,2、10,10,10,10,10,10。两位选手总分都是30按规则ID大的2应排在前面。输出2,1。ID范围边界测试ID0和ID99的情况。在IDE中设置断点观察playerScores这个map在分组后的内容确认数据是否正确归类。观察sortedScores排序后的结果确认取前三个的逻辑。观察validPlayers在排序前和排序后的内容验证自定义排序规则是否正确工作。6. 从解题到举一反三掌握同类问题模式这道“统计射击比赛成绩”题本质上是一类**“分组统计排序”**问题的典型代表。在华为OD机试乃至许多公司的笔试中这类问题非常常见。它的核心模式可以抽象为数据分组聚合根据某个Key如用户ID、商品类别、日期将一系列记录进行分组并对每组内的数据进行某种统计计算如求和、求平均、取Top N、计数等。按统计结果排序根据上一步计算出的聚合结果对所有组进行排序排序规则可能包含多个维度主排序条件、次排序条件。输出符合条件的结果可能还需要在排序前后进行过滤如本题中成绩数不足3的组被过滤掉。识别同类问题当你看到题目描述中出现“每个用户/商品/区域…”、“统计…”、“排名…”、“输出前N名…”等字眼时就要立刻联想到这个模式。例如“统计每个销售员的销售额按销售额降序输出销售额相同按工号升序输出。”“计算每个视频的播放量、点赞量、分享量加权总分按总分降序输出Top 10的视频ID。”“找出每个班级平均分最高的三位学生。”通用解题框架掌握了模式我们就可以总结出一个近乎模板化的解决框架// 1. 定义核心数据结构用于分组 unordered_mapKeyType, vectorValueType groupMap; // 或用 map 或用 array if key is small int // 2. 读取输入进行分组 while (有输入记录) { KeyType key 获取当前记录的key; ValueType value 获取当前记录的值; groupMap[key].push_back(value); } // 3. 定义结果容器遍历分组进行计算和过滤 vectorpairKeyType, AggregateResultType validResults; for (const auto [key, valueList] : groupMap) { // 过滤条件如数量不足 if (valueList.size() someThreshold) continue; // 聚合计算如求和、求平均、取TopN等 AggregateResultType result computeAggregation(valueList); // 存储合格结果 validResults.emplace_back(key, result); } // 4. 按自定义规则排序 sort(validResults.begin(), validResults.end(), [](const auto a, const auto b) { // 主排序条件 if (a.result ! b.result) return a.result b.result; // 降序 // 次排序条件 return a.key b.key; // 升序根据题目要求调整 }); // 5. 输出 // ...针对本题的变体思考如果题目要求变化我们只需要调整框架中的特定部分Top N变化如果不是取最高3个而是取最高5个只需修改循环中的数字3。聚合方式变化如果是求平均分则在计算result时求和后除以数量注意浮点数精度。过滤条件变化如果不是过滤数量而是过滤掉平均分低于60的选手则在计算result后判断。输出内容变化如果要求输出ID和总分而不仅仅是ID则在输出时同时输出pair的两个元素。对C容器的深入理解通过这道题我们强化了对std::map/std::unordered_map和std::vector的理解。map负责高效的分组归类vector负责存储和操作序列数据而pair和自定义排序则是连接数据与规则的桥梁。熟练掌握这些容器的特性和常用操作如push_back,sort,size, 范围for循环是解决大部分机试算法题的基础。最后这道题也提醒我们在编程时仔细阅读题目要求的重要性。规则中的每一个字“最高3个”、“少于3个无效”、“和相等按ID降序”都对应着代码中的一个判断或一个逻辑分支。养成将自然语言描述精确转化为代码逻辑的能力是通过这类机试的关键。多练习多总结把每一道做过的题都吃透比盲目刷很多题要有效得多。