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::map<int, std::vector<int>>作为核心数据结构？这是本题的关键决策。我们需要为每个选手存储他所有的射击成绩。选手ID是整数，并且范围给定（0-99），我们可以用数组，但使用std::map更具通用性和清晰性。map的键（Key）是选手ID，值（Value）是一个vector<int>，用来动态存储该选手的所有分数。这样，当我们遍历输入数据时，就可以很方便地将分数push_back到对应ID的vector中。即使某个ID第一次出现，map也会自动创建该键值对，其对应的vector初始为空，这省去了我们手动判断和初始化的麻烦。

计算逻辑的细化：

1. 数据收集与分组：同步遍历ID数组和分数数组，将分数插入到map[ID]对应的vector中。
2. 筛选与计算：遍历map中的每一个键值对（即每一位选手）：
   • 首先检查该选手的成绩数量（即vector的size()）是否大于等于3。如果小于3，直接跳过该选手。
   • 如果成绩数量足够，则对该选手的所有成绩进行降序排序（使用std::sort配合std::greater<int>()）。然后取排序后的前三个元素（即最高的三个分数）求和。
3. 排序与输出：计算完所有合格选手的总分后，我们需要根据总分进行排名。这里不能直接对map排序，因为map本身是按Key排序的。我们需要将数据转移到另一个容器中进行排序。通常我们会创建一个vector<pair<int, 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); vector<int> ids(N); vector<int> 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, 该选手所有成绩列表> map<int, vector<int>> playerScores; // 第一步：数据分组，将成绩按选手ID归类 for (int i = 0; i < N; ++i) { int playerId = ids[i]; int score = scores[i]; playerScores[playerId].push_back(score); } // 第二步：计算每位选手的最高三个成绩之和，并收集合格选手的信息 vector<pair<int, int>> validPlayers; // 存储<选手ID, 最高三成绩之和> for (const auto& entry : playerScores) { int playerId = entry.first; const vector<int>& scoreList = entry.second; // 规则2：成绩少于3个，忽略该选手 if (scoreList.size() < 3) { continue; } // 复制一份成绩列表进行排序，避免修改原数据（虽然这里修改了也不影响后续，但是个好习惯） vector<int> sortedScores = scoreList; // 降序排序，以便取前三个最高分 sort(sortedScores.begin(), sortedScores.end(), greater<int>()); // 计算最高三个成绩之和 int topThreeSum = 0; // 注意：这里使用min(3, sortedScores.size())是更安全的写法，虽然我们已经判断过size>=3 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 pair<int, int>& a, const pair<int, 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; }

关键代码段解析：

1. 输入处理：

   getline(cin, idLine); getline(cin, scoreLine);

   使用getline读取整行，因为输入是以逗号分隔的字符串。然后使用stringstream配合循环来解析每个整数，这是处理这类格式输入的常用且稳健的方法。

2. 数据分组：

   playerScores[playerId].push_back(score);

   这行代码是map妙用的体现。无论playerId是否已在map中，playerScores[playerId]都会返回一个vector<int>的引用（如果不存在则自动插入一个空vector），然后我们直接向这个vector中添加分数即可。

3. 成绩计算与筛选：

   if (scoreList.size() < 3) { continue; }

   这里严格执行了题目规则2。注意，我们是在遍历map时进行判断的，这意味着成绩少于3个的选手根本不会进入后续的validPlayers列表。

4. 自定义排序规则（Lambda表达式）：

   [](const pair<int, int>& a, const pair<int, int>& b) { if (a.second != b.second) { return a.second > b.second; } return a.first > b.first; }

   这是整个排序逻辑的核心。Lambda表达式清晰表达了我们的排序优先级：首先比较第二个元素（second，即总分），降序；如果相等，再比较第一个元素（first，即选手ID），也是降序。这个比较函数决定了sort算法如何排列元素。

5. 输出格式控制：

   if (i != validPlayers.size() - 1) { cout << ","; }

   这是一个常见的技巧，用于在输出序列元素时，只在元素之间打印分隔符（如逗号），避免在最后一个元素后多打印一个逗号，从而严格符合题目输出格式要求。

4. 算法复杂度分析与优化探讨

完成基本实现后，我们有必要分析一下代码的效率，并看看是否有优化空间。这对于机试中应对更大数据量的场景，或者理解算法本质都很有帮助。

时间复杂度分析：假设总射击次数为N，共有M位不同的选手。

1. 数据读取与解析：O(N)，这是必须的。
2. 数据分组：遍历N次，每次在map中查找或插入是O(log M)，所以这部分是O(N log M)。由于M最大为100（ID范围0-99），log M很小，近乎常数。
3. 成绩计算：遍历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会很大，但题目限制了N<=100，所以完全可接受。
4. 最终排序：对validPlayers（最多M个元素）排序，复杂度为O(M log M)。

综合来看，整个算法的时间复杂度主要由对每位选手的成绩列表进行排序这部分主导，即O(N log K)级别。在N=100的约束下，这个复杂度是瞬间完成的。

空间复杂度分析：我们主要存储了：

• playerScores(map): 存储了所有N个成绩，O(N)。
• validPlayers(vector): 最多存储M个元素，O(M)。
• 在计算过程中，为每位选手复制了一份成绩列表用于排序，这带来了额外的O(K)临时空间，但每个选手处理完后即释放。 总空间复杂度为O(N)。

潜在的优化点：虽然对于本题规模无需优化，但我们可以思考一下如果数据量变大（比如N上万），如何改进：

1. 避免全排序：我们只需要每个选手的前三大分数，而不需要整个有序列表。因此，可以使用一个大小为3的最小堆（Min-Heap）来维护当前遇到的最高三个分数。遍历一个选手的所有成绩时，将分数放入堆中，如果堆大小超过3，则弹出最小的那个。这样，处理K个成绩的时间复杂度可以从O(K log K)降低到O(K log 3)，即近似O(K)。C++中可以用priority_queue<int, vector<int>, greater<int>>来实现最小堆。
2. 输入优化：如果输入格式固定，可以使用更快的自定义解析函数来替代stringstream，但提升微乎其微。
3. 容器选择：由于选手ID范围固定且很小（0-99），我们可以直接用大小为100的数组vector<int> 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的确定性更有优势。

调试与测试建议：

1. 使用题目给的示例：首先用示例输入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。
2. 构造边界测试用例：
   • 所有选手成绩都少于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范围边界：测试ID=0和ID=99的情况。
3. 在IDE中设置断点：观察playerScores这个map在分组后的内容，确认数据是否正确归类。观察sortedScores排序后的结果，确认取前三个的逻辑。观察validPlayers在排序前和排序后的内容，验证自定义排序规则是否正确工作。

6. 从解题到举一反三：掌握同类问题模式

这道“统计射击比赛成绩”题，本质上是一类**“分组统计+排序”**问题的典型代表。在华为OD机试乃至许多公司的笔试中，这类问题非常常见。它的核心模式可以抽象为：

1. 数据分组聚合：根据某个Key（如用户ID、商品类别、日期）将一系列记录进行分组，并对每组内的数据进行某种统计计算（如求和、求平均、取Top N、计数等）。
2. 按统计结果排序：根据上一步计算出的聚合结果，对所有组进行排序，排序规则可能包含多个维度（主排序条件、次排序条件）。
3. 输出符合条件的结果：可能还需要在排序前后进行过滤（如本题中成绩数不足3的组被过滤掉）。

识别同类问题：当你看到题目描述中出现“每个用户/商品/区域…”、“统计…”、“排名…”、“输出前N名…”等字眼时，就要立刻联想到这个模式。例如：

• “统计每个销售员的销售额，按销售额降序输出，销售额相同按工号升序输出。”
• “计算每个视频的播放量、点赞量、分享量加权总分，按总分降序输出Top 10的视频ID。”
• “找出每个班级平均分最高的三位学生。”

通用解题框架：掌握了模式，我们就可以总结出一个近乎模板化的解决框架：

// 1. 定义核心数据结构：用于分组 unordered_map<KeyType, vector<ValueType>> groupMap; // 或用 map， 或用 array if key is small int // 2. 读取输入，进行分组 while (有输入记录) { KeyType key = 获取当前记录的key; ValueType value = 获取当前记录的值; groupMap[key].push_back(value); } // 3. 定义结果容器，遍历分组进行计算和过滤 vector<pair<KeyType, 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降序”）都对应着代码中的一个判断或一个逻辑分支。养成将自然语言描述精确转化为代码逻辑的能力，是通过这类机试的关键。多练习，多总结，把每一道做过的题都吃透，比盲目刷很多题要有效得多。