华为 10.21 机考非 AI 方向：故障域时标同步与数字分列最小差

《面试题目》

第 1 题 故障域时标同步（150 分）

整套装置里安放了 n 块转发芯片，编号 0 到 n-1；每块芯片有一个时标权重 w[i]。芯片之间通过链路互相传递时标信息，能够彼此走到的芯片组成一个「时标域」，域内权重最高的芯片成为时标源，若权重并列最高则取编号最小的那块；走不到任何其他芯片的芯片独自组成一个域，自己就是时标源。

现在大量链路损坏，装置裂成多个时标域。给定芯片数 n、仍保留的链路数 m、每块芯片的权重，以及 m 条双向链路（可能有重边和自环，不影响可达关系），再给定 q 次查询，每次问某块芯片当前跟随的时标源编号。要求输出这 q 个答案，空格分隔。

样例：5 块芯片、权重 4 1 4 7 2，链路 0-2、2-1、3-4，查询 2 4 1 0，输出 0 3 0 0。

第 2 题 数字分列最小差（150 分）

给定一列长度为 n 的正整数，每个数只取 1 到 9，可以重复出现。需要把这些数拆进两个部分，每边至少一个数、每个数正好用一次，两边各自占据的位置不必连续；同一边内部可以任意打乱顺序，再按书写顺序连成一个整数。记较大的整数为 A、较小的为 B，差为 A-B（只考虑非负）。

要求找出所有能使 A-B 最小的整数对：先输出最优整数对的数量，再按 A 从小到大逐行输出 A B 差值；不同的拆法如果拼出同一对整数，只保留一次。样例输入 2 和 7 2，输出 1 以及 7 2 5。

《参考解析》

1. 时标同步：并查集或 BFS 求连通块。 重边和自环不影响可达性，先把所有链路做并查集合并（或建邻接表跑 BFS/DFS），得到每个芯片所属的连通块编号。然后遍历所有芯片，对每个块维护「当前最大权重 + 对应编号」：权重更大就替换，权重相等时取编号更小的（w[i] > bestW || (w[i] == bestW && i < bestId)）。最后每次查询 O(1) 查表输出。并查集版本复杂度 O((n + m) α(n) + q)，BFS 版本 O(n + m + q)，都远优于「每次查询重新遍历」。实现细节：初始化 parent[i] = i，find 带路径压缩，union 按秩合并；自环 u == v 直接跳过；重边重复 union 无影响。若权重和编号范围很大，注意用 64 位整数存权重。

2. 数字分列：子集枚举 + 去重全排列。 每个数字只能进 A 组或 B 组，所以先二进制枚举划分（mask 表示进 A 的下标集合），mask 为 0 或全 1 时有一边为空、跳过；左右互换是同一个划分，只处理 mask 较小的那一次。对每一边，把数字排序后用 next_permutation 生成所有不重复的排列并拼成整数——重复数字不会产生新排列，天然去重。然后两边的整数集合两两配对，算 |x - y|：比当前最优小就清空结果集合并更新，等于就加入集合（用 set 去重）。最后按 A 升序输出。复杂度最坏是 O(2^n · n! · n!)，只在 n 很小的时候可行；题面原始的数据范围在原文里排版丢失（样例 n=2），如果 n 到十几以上，这个暴力会超时，需要换思路：先按位数把数字分成尽量接近的两半，再在组内做「大数配小数」的贪心 + 局部交换搜索，或者用 meet-in-the-middle。

3. 两道题的共同易错点。 第一题是「并列取最小」和「孤立点自成一域」——孤立点没有链路，但仍要参与查询，别只遍历出现过端点的芯片。第二题是「拼接不是相加」和「同一边可任意排列」——如果按原顺序拼、或者把两组数字相加来比，结果完全不同；另外输出要求是「所有最优对」而不是只输出一个，且要去重、按 A 升序，格式错会直接 0 分。考场上建议先用小样例手算验证去重逻辑（比如 1 1、1 2 3、9 1 这几种），再提交。