2026 华为OD机试真题 4月22日华为OD上机新系统考试真题 200 分题型

点击查看华为 OD 机试真题完整目录：2026最新华为OD机试新系统卷 + 双机位C卷 真题题库目录｜全覆盖题库 + 逐点算法考点详解

题目描述

9月份开学第一天，小学某班级进行班长选举活动，班级共有$N$个学生，每个学生最多可投$3$票（对同一个人只能投一票），也可以弃权不投票，大家投票时写上对应学生的名字（假设学生不存在重名，考虑到部分少数民族名字带分隔，且整体较长，同学在投票时为了方便，允许同学写全称，也可以只写其中的部分连续段，比如班级里只有$2$个少数民族名称带点的同学，$A$同学叫买买提-艾尔肯-巴图尔，$B$同学叫买买提-艾尔肯-库尔班，那要给$A$同学投票，可以写 买买提-艾尔肯-巴图尔 或者 艾尔肯-巴图尔 或者 巴图尔，但是不能写 买买、买买提-艾、肯-库尔班、肯-库这种某名字未写全的情况），学生可以把票投给自己。

得票最多的同学当选班长，如果票数相同，则按名字做字符串排序，排序靠前的当选班长。

如果选票上写的名字不合理（要求投票的名字必需是连续的，少数民族可以是连续的若干段，但要求每段名称要写全，选票上的名字需要能唯一匹配某个人），则认为是无效票，直接忽略。

如果出现原始输入总选票数超过$3$倍班级总人数、某位同学的得票数超过班级总人数、没有一个同学被选中这些情况，则认为选举无效，返回固定字符串 "Invalid election."。

现在投票环节已完成，进入唱票环节，请你完善代码根据投票数据，给出当选班长对应的完整名称。 方法共$2$个参数，第一个参数是全班同学的名称集合，第二个参数是选票数据集合。

考虑到部分语言对中文处理不太友好，名称输入统一为普通的ASCII字符，选票中少数民族名称中的连接符（$\cdot$）改用英文横杠连接符($-$)。

输入描述

输入为一行，包含两个参数，分别是全班同学的名称集合和选票数据集合，以逗号分隔。每个集合用方括号 [] 包围，元素用双引号 "" 包围并以逗号分隔。

例如：["Zhangsan", "Lisi", "Wangwu"],["Zhangsan", "Lisi", "Zhangsan"]

输出描述

当选班长的完整名称

示例1

输入

["Zhangsan", "Lisi", "Wangwu"],["Zhangsan", "Lisi", "Zhangsan"]

输出

Zhangsan

说明

Zhangsan得$2$张选票，Lisi只得$1$张选票，Zhangsan票数更高，因此Zhangsan当选班长。

示例2

输入

["Zhangsanfeng", "Zhangsande"],["Zhangsan", "Zhangsande", "Zhangsan"]

输出

Zhangsande

说明

虽然Zhangsan有$2$张选票，由于不属于班级成员，对应选票无效，因此获得$1$张选票的Zhangsande当选班长。

示例3

输入

["maimaiti-aierken-batuer", "maimaiti-aierken-kuerban"],["batuer", "aierken-batuer", "maimaiti", "maimaiti-aierken-kuerban"]

输出

maimaiti-aierken-batuer

说明

"batuer"和"aierken-batuer"都能唯一匹配"maimaiti-aierken-batuer"，因此"maimaiti-aierken-batuer"获得$2$票，"maimaiti"因为有多个名字都匹配，认定为无效票。"maimaiti-aierken-kuerban"能唯一匹配，获得$1$票，所以得票更多的"maimaiti-aierken-batuer"当选班长。

解题思路

核心思想

1. 预处理名字匹配映射：

   • 为了快速判断选票上的名字是否能唯一匹配某个学生，我们可以对全班每个学生的名字进行预处理。
   • 每个名字按连字符 - 分割成若干段。合法的缩写必须是这些段的连续组合（例如 A-B-C 的合法缩写有 A, B, C, A-B, B-C, A-B-C）。
   • 使用一个哈希表 mapping 记录每个合法的缩写对应的完整名字。
   • 如果一个缩写对应多个不同的完整名字，则在哈希表中标记为无效（例如 #INVALID#），表示存在歧义。

2. 投票规则校验：

   • 总票数校验：总选票数不能超过全班人数 $N$ 的 3 倍。
   • 唯一匹配校验：选票上的名字必须在 mapping 中存在且不具有歧义。
   • 得票数校验：统计每位学生的有效得票数，任何一位学生的得票数不能超过全班总人数 $N$。
   • 空选举校验：如果没有产生任何有效选票，选举无效。

3. 确定当选者：

   • 在所有获得有效选票的学生中，选出得票数最多的。
   • 如果票数相同，则按照名字的字典序进行升序排序，选择排序靠前者。

复杂度分析

• 时间复杂度：$O(N \cdot M^2 + T)$，其中 $N$ 是学生人数，$M$ 是名字的最大分段数（通常很小），$T$ 是选票总数。预处理每个名字的连续段需要 $O(M^2)$，处理所有选票需要 $O(T)$。
• 空间复杂度：$O(N \cdot M^2)$，用于存储名字缩写映射的哈希表。