20260708-计算碳排放减少量（N0043）- 算法机考高频题型 · 算法题解 | AlgoMooc

N0043. 20260708-计算碳排放减少量

中等

通过率 86% · 提交 14 · 通过 12

本题改编自算法机考高频题型 · 考点：算法 · 难度：中等

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

这类题属于算法机考高频题型中「算法」方向的高频题型，通常考察对「算法」的建模能力与边界条件处理。掌握本题的解题思路后，可举一反三应对同类真题方向，稳步提升机考通过率。

输入描述

整型数组 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[j][0], edges[j][1] ≤ N-1
edges[j][0] != edges[j][1]，无重复边

输出描述

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

示例

示例 1

输入示例

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

输出示例

说明：

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 碳交易区A减排量更大，输出 14

示例 2

输入示例

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

输出示例

说明：

3个区域连为1个碳交易区：绿色减排总量=3+5+7=15，碳排放总量=6+4+2=12，减排量=(15-12)×3=9，输出9

示例 3

输入示例

3
2,4,6
2,4,6
0

输出示例

-1

说明：

每个区域独立，不构成有效碳交易区，输出-1

时间限制 1000 ms · 内存限制 256 MB

本平台为独立第三方培训机构，与华为技术有限公司无任何关联；课程的服务内容与权益以购买协议为准，学习效果因个人情况而异。「华为 OD」「华为可信」等仅为对岗位与考试方向的客观描述，相关商标归各自权利人所有。

问小欧 · 图解算法年卡¥99 开通 →

字号13Ctrl+/ 注释 · Ctrl+↵ 提交

from typing import List
from collections import deque, defaultdict


# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
# @param green: 整型数组，长度为N，表示编号0~N-1的区域绿色能源减排量（吨）
# @param carbon: 整型数组，长度为N，表示编号0~N-1的区域化石能源碳排放量（吨）
# @param edges: 二维整型数组，每行2个整数，表示该线路连接的两个区域编号
# @return: 整型，表示所有碳交易区中减排量的最大值，若无有效碳交易区输出-1
class Solution:
    def bfs(self, start, green, carbon, neighbor_dic, checklist):
        pass

    def dfs(self, node, green, carbon, neighbor_dic, checklist):
        pass

    def dfs_start(self, start, green, carbon, neighbor_dic, checklist):
        pass

    def maxReduction(self, green: List, carbon: List, edges: List[List]) -> int:
        pass


# 以下内容为LeetCode核心代码模式转为ACM模式所需代码
# 请在algomooc oj上直接使用，在实际考试中无需编写

def main():
    import sys
    input = sys.stdin.readline

    n = int(input().strip())
    green = list(map(int, input().strip().split(',')))
    carbon = list(map(int, input().strip().split(',')))
    m = int(input().strip())
    edges = []
    for _ in range(m):
        line = input().strip()
        if not line:
            continue
        u, v = map(int, line.split(','))
        edges.append([u, v])

    sol = Solution()
    print(sol.maxReduction(green, carbon, edges))


if __name__ == "__main__":
    main()

from typing import List
from collections import deque, defaultdict

# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
# @param green: 整型数组，长度为N，表示编号0~N-1的区域绿色能源减排量（吨）
# @param carbon: 整型数组，长度为N，表示编号0~N-1的区域化石能源碳排放量（吨）
# @param edges: 二维整型数组，每行2个整数，表示该线路连接的两个区域编号
# @return: 整型，表示所有碳交易区中减排量的最大值，若无有效碳交易区输出-1
class Solution:
    def bfs(self, start, green, carbon, neighbor_dic, checklist):
        pass

def dfs(self, node, green, carbon, neighbor_dic, checklist):
        pass

def dfs_start(self, start, green, carbon, neighbor_dic, checklist):
        pass

def maxReduction(self, green: List, carbon: List, edges: List[List]) -> int:
        pass

# 以下内容为LeetCode核心代码模式转为ACM模式所需代码
# 请在algomooc oj上直接使用，在实际考试中无需编写

def main():
    import sys
    input = sys.stdin.readline

n = int(input().strip())
    green = list(map(int, input().strip().split(',')))
    carbon = list(map(int, input().strip().split(',')))
    m = int(input().strip())
    edges = []
    for _ in range(m):
        line = input().strip()
        if not line:
            continue
        u, v = map(int, line.split(','))
        edges.append([u, v])

sol = Solution()
    print(sol.maxReduction(green, carbon, edges))

if __name__ == "__main__":
    main()

写完代码点「提交」，将对全部测试用例判题。

输入描述

输出描述

示例

我的提交