2026 华为OD机试真题 7月8日华为OD上机新系统考试真题 100 分题型

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

题目描述

某能源集团管理 N 个区域（编号 0\~N−1），每个区域有绿色能源减排量和化石能源碳排放量（单位均为吨）。区域间通过 M 条输电线路连接，相连区域属于同一碳交易区。在同一碳交易区内，绿色减排量可跨区域抵消碳排放区，区内总减排量 = max(0,绿色减排量总量−化石能源碳排放量总量)× 区内区域数。请输出所有碳交易区中减排量的最大值。若无有效碳交易区（区域数 <2 或 M=0），输出 −1。

2026 华为OD机试真题 7月8日华为OD上机新系统考试真题 100 分题型

输入描述

整数数组 green，长度为 N，表示编号 0\~N−1 的区域绿色能源减排量（吨）；

整数数组 carbon，长度为 N，表示编号 0\~N−1 的区域化石能源碳排放量（吨）；

二维整数数组 edges，每行 2 个整数，表示该线路连接的两个区域编号，共 M 行。

约束：

• 1≤N≤100
• 0≤M≤N×(N−1)/2
• 0≤green[i]≤10000
• 0≤carbon[i]≤10000
• 0≤edges[i][0],edges[i][1]≤N−1
• edges[i][0]\=edges[i][1]，无重复边

输出描述

整数，表示所有碳交易区中减排量的最大值。若无有效碳交易区，输出 −1。

示例1

输入

[5,8,3,10],[4,2,6,9],[[0,1],[2,3]]

输出

14

说明

• 4 个区域，green = [5,8,3,10]，carbon = [4,2,6,9]

• 边 (0,1) 将区域 0,1 连为碳交易区 A：

  • 绿色减排总量 =5+8=13
  • 碳排放总量 =4+2=6
  • 减排量 =(13−6)×2=14

• 边 (2,3) 将区域 2,3 连为碳交易区 B：

  • 绿色减排总量 =3+10=13
  • 碳排放总量 =6+9=15
  • 减排量 =max(0,13−15)×2=0

• 最大减排量为 14

示例2

输入

[3,5,7],[6,4,2],[[0,1],[1,2]]

输出

9

说明

3 个区域全连通为 1 个碳交易区：

• 绿色减排总量 =3+5+7=15
• 碳排放总量 =6+4+2=12
• 减排量 =(15−12)×3=9

示例3

输入

[2,4,6],[2,4,6],[]

输出

-1

说明

无有效碳交易区

解题思路

核心思想

利用并查集将相连的区域合并为连通分量，然后对每个连通分量计算碳减排量。减排量 = max(0, 绿色减排总量 - 碳排放总量) × 区域数。

算法步骤

1. 边界判断：若区域数 < 2 或无输电线路，返回 -1
2. 并查集初始化：每个区域为自己的父节点
3. 合并连通分量：遍历所有边，合并相连区域
4. 聚合数据：遍历所有区域，按根节点聚合绿色减排量、碳排放量和区域计数
5. 计算减排量：对区域数 >= 2 的连通分量，计算减排量并取最大值

复杂度分析

• 时间复杂度：O(N + M)，主要来自并查集的合并和查找操作
• 空间复杂度：O(N)，用于存储并查集和