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

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

题目描述

某电力公司管理N个变电站节点（编号0~N-1），节点间通过M条输电线路连接，相连节点属于同一供电区。定义供电区的不均衡度=区内最大负载与最小负载之差 ×节点数。请找出不均衡度最大的供电区，输出其不均衡度。若无有效供电区（节点数<2或M=0），输出-1。

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

输入描述

整型数组loads，长度为N，表示编号0~N-1的节点负载(MW); 二维整型数组edges，每行2个整数，表示该线路连接的两个节点编号，共M行。

约束:

1 ≤ N ≤ 100 0 ≤ M ≤ N×(N-1)/2 0 ≤ loads[i] ≤ 10000 0 ≤ edges[j][0], edges[j][1] ≤ N-1 edges[j][0] ≠ edges[j][1]，无重复边

输出描述

整型，表示所有供电区中不均衡度的最大值。若无有效供电区，输出-1。

示例1

输入

[100,200,150,50,300],[[0,1],[1,2],[3,4]]

输出

500

说明

边(0,1)(1,2)将节点0,1,2连为供电区A，负载[100,200,150]，不均衡度=(200-100)×3=300 边(3,4)将节点3,4连为供电区B，负载[50,300]，不均衡度=(300-50)×2=500 供电区B不均衡度更大，输出500

示例2

输入

[80,90,80,90],[[0,1],[1,2],[2,3]]

输出

40

说明

4个节点连为1个供电区，不均衡度=(90-80)×4=40，输出40

示例3

输入

[100,200,300],[]

输出

-1

说明

每个节点独立，不构成有效供电区，输出-1

解题思路

核心思想

本题是一个 图的连通分量 问题，需要使用 并查集（Union-Find） 算法来找出所有供电区，然后计算每个供电区的不均衡度。

算法步骤：

1. 初始化并查集，每个节点独立为一个集合
2. 遍历所有边，将相连的节点合并到同一个集合
3. 将同一集合的节点分组
4. 对每个分组：
   • 节点数 < 2 的跳过（不是有效供电区）
   • 计算负载最大值和最小值
   • 计算不均衡度 = (最大值 - 最小值) × 节点数
5. 返回最大不均衡度，如果没有有效供电区返回 -1

并查集核心操作：

• find(x)：查找节点 x 所属集合的根节点（路径压缩优化）
• union(a, b)：合并节点 a 和 b 所在的集合

复杂度分析

• 时间复杂度：O(N + M × α(N))，α 为 Ackermann 函数的反函数，近似常数
• 空间复杂度：O(N)，存储