【华为OD-E卷-AI处理器组合100分（python、java、c++、js、c）】

题目

某公司研发了一款高性能AI处理器。每台物理设备具备8颗AI处理器，编号分别为0、1、2、3、4、5、6、7。
编号0-3的处理器处于同一个链路中，编号4-7的处理器处于另外一个链路中，不通链路中的处理器不能通信。如下图所示：
现给定服务器可用的处理器编号数组array，以及任务申请的处理器数量num，找出符合下列亲和性调度原则的芯片组合。
如果不存在符合要求的组合，则返回空列表。
亲和性调度原则：
如果申请处理器个数为1，则选择同一链路，剩余可用的处理器数量为1个的最佳，其次是剩余3个的为次佳，然后是剩余2个，最后是剩余4个。如果申请处理器个数为2，则选择同一链路剩余可用的处理器数量2个的为最佳，其次是剩余4个，最后是剩余3个。如果申请处理器个数为4，则必须选择同一链路剩余可用的处理器数量为4个。如果申请处理器个数为8，则申请节点所有8个处理器。提示：
任务申请的处理器数量只能是1、2、4、8。编号0-3的处理器处于一个链路，编号4-7的处理器处于另外一个链路。处理器编号唯一，且不存在相同编号处理器。

输入描述

输入包含可用的处理器编号数组array，以及任务申请的处理器数量num两个部分。

第一行为array，第二行为num。例如：

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

表示当前编号为0、1、4、5、6、7的处理器可用。任务申请1个处理器。

0 <= array.length <= 8 0 <= array[i] <= 7 num in [1, 2, 4, 8] 输出描述输出为组合列表，当array=[0，1，4，5，6，7]，num=1 时，输出为[[0], [1]]。

用例

用例一：

输入：

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

输出：

[[0], [1]]

用例二：

输入：

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

输出：

[[4, 5, 6, 7]]

说明

根据第三条亲和性调度原则，必须选择同一链路剩余可用的处理器数量为4个的环

python解法

解题思路：
这个问题是关于处理一个数组 arr，并根据给定的数字 num 对该数组进行不同方式的调度。调度的方式依赖于以下几个步骤：

初始化与分组：首先将输入数组 arr 排序，然后将数组中的元素分成两个子列表 link1 和 link2，其中 link1 包含所有小于4的元素，link2 包含所有大于等于4的元素。

调度规则：根据输入的 num 值，决定如何处理这两个子列表：

num = 1：选择长度为 1、2、3 或 4 的组合进行调度。
num = 2：选择长度为 2、3 或 4 的组合进行调度。
num = 4：只调度长度为 4 的子列表。
num = 8：如果 link1 和 link2 都有长度为 4 的元素，将它们合并并进行调度。
深度优先搜索（DFS）：使用递归的 DFS 方法来枚举 link1 和 link2 中所有可能的子集组合，根据 num 的值来决定每次深度遍历的层数。每次递归都会生成不同长度的组合，并最终返回所有可能的调度结果。

class ProcessorScheduler:def __init__(self, arr, num):# 初始化，arr是输入的数组，num是调度的规则self.arr = sorted(arr)  # 排序输入数组self.num = num  # 设定调度规则self.link1 = []  # 小于4的元素self.link2 = []  # 大于等于4的元素self.result = []  # 存储调度结果def split_links(self):# 根据元素大小将arr分成两个子列表for e in self.arr:if e < 4:self.link1.append(e)else:self.link2.append(e)def schedule(self):# 根据num值来选择调度方式self.split_links()  # 先分组len1 = len(self.link1)len2 = len(self.link2)if self.num == 1:self._schedule_one(len1, len2)elif self.num == 2:self._schedule_two(len1, len2)elif self.num == 4:self._schedule_four(len1, len2)elif self.num == 8:self._schedule_eight(len1, len2)return self.resultdef _schedule_one(self, len1, len2):# 处理num为1的情况，根据长度分别递归调度if len1 == 1 or len2 == 1:if len1 == 1:self._dfs(self.link1, 1)if len2 == 1:self._dfs(self.link2, 1)elif len1 == 3 or len2 == 3:if len1 == 3:self._dfs(self.link1, 1)if len2 == 3:self._dfs(self.link2, 1)elif len1 == 2 or len2 == 2:if len1 == 2:self._dfs(self.link1, 1)if len2 == 2:self._dfs(self.link2, 1)elif len1 == 4 or len2 == 4:if len1 == 4:self._dfs(self.link1, 1)if len2 == 4:self._dfs(self.link2, 1)def _schedule_two(self, len1, len2):# 处理num为2的情况，根据长度分别递归调度if len1 == 2 or len2 == 2:if len1 == 2:self._dfs(self.link1, 2)if len2 == 2:self._dfs(self.link2, 2)elif len1 == 4 or len2 == 4:if len1 == 4:self._dfs(self.link1, 2)if len2 == 4:self._dfs(self.link2, 2)elif len1 == 3 or len2 == 3:if len1 == 3:self._dfs(self.link1, 2)if len2 == 3:self._dfs(self.link2, 2)def _schedule_four(self, len1, len2):# 处理num为4的情况，只调度长度为4的子列表if len1 == 4:self.result.append(self.link1)if len2 == 4:self.result.append(self.link2)def _schedule_eight(self, len1, len2):# 处理num为8的情况，如果link1和link2都有长度为4的元素，合并调度if len1 == 4 and len2 == 4:self.result.append(self.link1 + self.link2)def _dfs(self, arr, level):# 通过深度优先搜索枚举所有可能的组合path = []self._dfs_helper(arr, 0, level, path)def _dfs_helper(self, arr, index, level, path):# 递归函数，生成长度为level的子集if len(path) == level:self.result.append(path[:])  # 如果路径长度符合条件，保存该组合returnfor i in range(index, len(arr)):path.append(arr[i])  # 选择当前元素self._dfs_helper(arr, i + 1, level, path)  # 递归选择下一个元素path.pop()  # 回溯，移除当前元素if __name__ == "__main__":arr = eval(input())  # 输入数组num = int(input())  # 输入调度规则scheduler = ProcessorScheduler(arr, num)print(scheduler.schedule())  # 输出调度结果

java解法

解题思路
该题目要求根据给定的数组和一个调度级别 num，从数组中生成符合条件的组合。具体而言，数组中的元素根据大小被分为两组：link1（包含小于 4 的元素）和 link2（包含大于等于 4 的元素）。根据不同的调度级别 num，选择合适的组合方式：

调度级别为 1 或 2：

从 link1 和 link2 中分别生成大小为 num 的所有组合。
调度级别为 4：

如果 link1 或 link2 中有正好 4 个元素，将其加入结果。
调度级别为 8：

如果 link1 和 link2 都有 4 个元素，则将两者合并，并将合并后的结果加入到结果中。

import java.util.*;public class Main {public static void main(String[] args) {Scanner sc = new Scanner(System.in);// 读取输入数组并将其转换为 Integer 数组Integer[] arr = Arrays.stream(sc.nextLine().split("[\\[\\]\\,\\s]")).filter(str -> !"".equals(str))  // 去除空字符串.map(Integer::parseInt)  // 转换为整数.toArray(Integer[]::new);  // 转换为 Integer 数组// 读取调度级别 numint num = sc.nextInt();// 调用 findProcessorCombinations 方法计算并打印结果System.out.println(findProcessorCombinations(arr, num));}// 主计算方法：根据调度级别生成符合条件的组合public static List<List<Integer>> findProcessorCombinations(Integer[] arr, int num) {List<List<Integer>> result = new ArrayList<>();  // 存储最终结果List<Integer> link1 = new ArrayList<>();  // 存储小于4的元素List<Integer> link2 = new ArrayList<>();  // 存储大于等于4的元素// 遍历数组，将元素根据大小分配到 link1 或 link2 中for (int p : arr) {if (p < 4) {link1.add(p);  // 小于4的元素加入 link1} else {link2.add(p);  // 大于等于4的元素加入 link2}}// 根据调度级别调用不同的生成组合的方法if (num == 1 || num == 2) {findCombinations(link1, num, result);  // 从 link1 中找大小为 num 的组合findCombinations(link2, num, result);  // 从 link2 中找大小为 num 的组合} else if (num == 4) {// 如果 link1 或 link2 有正好 4 个元素，将其加入结果if (link1.size() == 4) result.add(new ArrayList<>(link1));if (link2.size() == 4) result.add(new ArrayList<>(link2));} else if (num == 8 && link1.size() == 4 && link2.size() == 4) {// 如果 link1 和 link2 都有 4 个元素，合并它们List<Integer> combined = new ArrayList<>(link1);combined.addAll(link2);result.add(combined);}return result;  // 返回最终的组合结果}// 找到从 link 中选取 num 个元素的所有组合private static void findCombinations(List<Integer> link, int num, List<List<Integer>> result) {if (link.size() >= num) {// 如果 link 中的元素数量大于或等于 num，调用回溯算法生成所有组合backtrack(link, new ArrayList<>(), 0, num, result);}}// 回溯算法：生成所有符合条件的组合private static void backtrack(List<Integer> link, List<Integer> current, int start, int num, List<List<Integer>> result) {if (current.size() == num) {// 如果当前组合的大小等于 num，将其加入结果result.add(new ArrayList<>(current));return;}// 遍历 link 中的元素，生成组合for (int i = start; i < link.size(); i++) {current.add(link.get(i));  // 将当前元素加入组合backtrack(link, current, i + 1, num, result);  // 递归生成剩余的组合current.remove(current.size() - 1);  // 回溯，移除最后一个元素}}
}