【华为OD机试】处理器问题

输入	[0, 1, 4, 5, 6, 7] 1
输出	[[0], [1]]
说明	根据第一条亲和性调度原则，在剩余两个处理器的链路（0, 1, 2, 3）中选择处理器。由于只有0和1可用，则返回任意一颗处理器即可。

输入	[0, 1, 4, 5, 6, 7] 4
输出	[[4, 5, 6, 7]]
说明	根据第三条亲和性调度原则，必须选择同一链路剩余可用的处理器数量为4个的环

考察算法：深度优先搜索

题目解析

题目要求根据给定的可用处理器编号数组和任务申请的处理器数量，找出符合亲和性调度原则的芯片组合。

根据题目描述，我们可以将问题分解为以下几个步骤：

根据可用的处理器编号数组，确定每个链路上可用的处理器数量。
根据任务申请的处理器数量和亲和性调度原则，确定最佳的芯片组合策略。
根据最佳的芯片组合策略，从可用的处理器中选择合适的芯片组合。

下面是对每个步骤的详细分析：

步骤1：确定每个链路上可用的处理器数量

根据题目描述，处理器编号0-3处于同一个链路中，处理器编号4-7处于另外一个链路中。因此，我们需要统计每个链路上可用的处理器数量。

我们可以使用两个计数器分别统计两个链路上可用的处理器数量。遍历可用的处理器编号数组，如果处理器编号在0-3之间，则将第一个计数器加1；如果处理器编号在4-7之间，则将第二个计数器加1。

步骤2：确定最佳的芯片组合策略

根据亲和性调度原则，我们需要根据任务申请的处理器数量来确定最佳的芯片组合策略。

如果申请处理器个数为1，则选择同一链路，剩余可用的处理器数量为1个的最佳，其次是剩余3个的为次佳，然后是剩余2个，最后是剩余4个。
如果申请处理器个数为2，则选择同一链路剩余可用的处理器数量2个的为最佳，其次是剩余4个，最后是剩余3个。
如果申请处理器个数为4，则必须选择同一链路剩余可用的处理器数量为4个。
如果申请处理器个数为8，则申请节点所有8个处理器。

根据上述原则，我们可以根据任务申请的处理器数量和每个链路上可用的处理器数量，确定最佳的芯片组合策略。

步骤3：选择合适的芯片组合

根据最佳的芯片组合策略，我们可以从可用的处理器中选择合适的芯片组合。

如果申请处理器个数为1，则根据最佳策略选择一个合适的处理器。
如果申请处理器个数为2，则根据最佳策略选择两个合适的处理器。
如果申请处理器个数为4，则根据最佳策略选择四个合适的处理器。
如果申请处理器个数为8，则选择所有可用的处理器。

最后，将选择的芯片组合添加到结果列表中，并返回结果列表。

算法实现

实现一：


# 输入获取
input_arr = eval(input())  # 将输入的第一行作为可用处理器编号数组 arr
input_num = int(input())  # 将输入的第二行作为任务申请的处理器数量 num
# 算法入口
def get_result(arr, num):
    """
    该函数是处理器分配算法的主函数，它接受以下两个参数：
    - arr: 可用处理器编号的列表，表示系统中所有可用的处理器编号。
    - num: 任务申请的处理器数量，表示任务需要使用的处理器数量。
    函数内部首先将可用处理器编号按照升序排序，然后根据处理器编号将它们划分为两个链路（编号小于4的归为链路1，大于等于4的归为链路2）。
    接下来，根据任务申请的处理器数量和一些预定的规则，使用深度优先搜索函数 dfs 来生成符合要求的处理器组合，并将结果存储在列表 ans 中。
    最后，函数返回 ans 作为结果。
    """
    link1 = []  # 存储链路1中可用的处理器编号
    link2 = []  # 存储链路2中可用的处理器编号
    arr.sort()  # 对可用处理器编号数组进行排序
    for e in arr:
        if e < 4:
            link1.append(e)  # 如果处理器编号小于4，则添加到链路1中
        else:
            link2.append(e)  # 如果处理器编号大于等于4，则添加到链路2中
    ans = []  # 存储符合要求的芯片组合
    len1 = len(link1)  # 计算链路1中可用的处理器数量
    len2 = len(link2)  # 计算链路2中可用的处理器数量
    # 根据任务申请的处理器数量和亲和性调度原则进行处理
    if num == 1:
        # 如果申请处理器个数为1，则选择同一链路，剩余可用的处理器数量为1个的最佳，其次是剩余3个的为次佳，然后是剩余2个，最后是剩余4个。
        if len1 == 1:
            dfs(link1, 0, 1, [], ans)
        elif len2 == 1:
            dfs(link2, 0, 1, [], ans)
        elif len1 == 3:
            dfs(link1, 0, 1, [], ans)
        elif len2 == 3:
            dfs(link2, 0, 1, [], ans)
        elif len1 == 2:
            dfs(link1, 0, 1, [], ans)
        elif len2 == 2:
            dfs(link2, 0, 1, [], ans)
        elif len1 == 4:
            dfs(link1, 0, 1, [], ans)
        elif len2 == 4:
            dfs(link2, 0, 1, [], ans)
    elif num == 2:
        # 如果申请处理器个数为2，则选择同一链路剩余可用的处理器数量2个的为最佳，其次是剩余4个，最后是剩余3个。
        if len1 == 2:
            dfs(link1, 0, 2, [], ans)
        elif len2 == 2:
            dfs(link2, 0, 2, [], ans)
        elif len1 == 4:
            dfs(link1, 0, 2, [], ans)
        elif len2 == 4:
            dfs(link2, 0, 2, [], ans)
        elif len1 == 3:
            dfs(link1, 0, 2, [], ans)
        elif len2 == 3:
            dfs(link2, 0, 2, [], ans)
    elif num == 4:
        # 如果申请处理器个数为4，则必须选择同一链路剩余可用的处理器数量为4个。
        if len1 == 4:
            ans.append(link1)
        elif len2 == 4:
            ans.append(link2)
    elif num == 8:
        # 如果申请处理器个数为8，则申请节点所有8个处理器。
        if len1 == 4 and len2 == 4:
            tmp = link1 + link2  # 将两个链路的处理器编号合并到一个列表中
            ans.append(tmp)
    return ans
# 深度优先搜索函数，用于生成符合要求的芯片组合
def dfs(arr, index, level, path, res):
    """
    该函数是深度优先搜索函数，它接受以下五个参数：
    - arr: 当前链路的可用处理器编号列表，表示在当前链路中所有可用的处理器编号。
    - index: 当前搜索的起始位置，表示从 arr 中的哪个位置开始搜索。
    - level: 任务申请的处理器数量，表示任务需要使用的处理器数量。
    - path: 当前的路径，表示已经选择的处理器编号列表。
    - res: 结果列表，表示符合要求的处理器组合列表。
    函数通过递归的方式，从当前位置开始，依次尝试将每个可用的处理器编号添加到路径中，并继续递归搜索。
    如果当前路径的长度达到任务申请的处理器数量，则将该路径添加到结果列表中。
    最后，通过回溯的方式，将当前处理器编号从路径中删除，并继续尝试其他可能的组合。
    """
    if len(path) == level:  # 如果路径长度达到要求的处理器数量，则将路径添加到结果列表中
        res.append(path[:])
        return
    for i in range(index, len(arr)):
        path.append(arr[i])  # 将当前处理器编号添加到路径中
        dfs(arr, i + 1, level, path, res)  # 递归调用 dfs 函数
        path.pop()  # 回溯，将当前处理器编号从路径中删除
# 算法调用
print(get_result(input_arr, input_num))  # 调用 get_result 函数并打印结果

代码实现思路如下：

算法入口：get_result 函数

接受两个参数：arr表示可用处理器编号的列表，num表示任务申请的处理器数量。
将可用处理器编号按照升序排序。
根据处理器编号将它们划分为两个链路：编号小于4的归为链路1，大于等于4的归为链路2。
根据任务申请的处理器数量和一些预定的规则，使用深度优先搜索函数 dfs 来生成符合要求的处理器组合，并将结果存储在列表 ans 中。
返回 ans 作为结果。

深度优先搜索函数：dfs

接受五个参数：arr表示当前链路的可用处理器编号列表，index表示当前搜索的起始位置，level表示任务申请的处理器数量，path表示当前的路径，res表示结果列表。
通过递归的方式，从当前位置开始，依次尝试将每个可用的处理器编号添加到路径中，并继续递归搜索。
如果当前路径的长度达到任务申请的处理器数量，则将该路径添加到结果列表中。
最后，通过回溯的方式，将当前处理器编号从路径中删除，并继续尝试其他可能的组合。

算法调用

从标准输入获取可用处理器编号数组和任务申请的处理器数量。
调用 get_result 函数，并将结果打印出来。

实现二：


def get_result(arr, num):
    """
    该函数根据任务申请的处理器数量和亲和性调度原则，从可用处理器编号数组中选择最佳的处理器组合。
    :param arr: 可用处理器编号数组，已排序。
    :param num: 任务申请的处理器数量。
    :return: 符合要求的处理器组合列表。
    """
    # 初始化两个列表，分别用于存储链路1和链路2中可用的处理器编号。
    link1 = []
    link2 = []
    # 遍历可用处理器编号数组，将处理器编号小于4的添加到链路1中，大于等于4的添加到链路2中。
    for e in arr:
        if e < 4:
            link1.append(e)
        else:
            link2.append(e)
    # 初始化结果列表，用于存储符合要求的处理器组合。
    ans = []
    # 计算链路1和链路2中可用的处理器数量。
    len1 = len(link1)
    len2 = len(link2)
    # 根据任务申请的处理器数量进行不同情况的处理。
    if num == 1:
        # 如果申请处理器个数为1，则选择同一链路，剩余可用的处理器数量为1个的最佳，其次是剩余3个的为次佳，然后是剩余2个，最后是剩余4个。
        if len1 == 1:
            ans.append(link1)
        elif len2 == 1:
            ans.append(link2)
        elif len1 == 3:
            ans.append(link1)
        elif len2 == 3:
            ans.append(link2)
        elif len1 == 2:
            ans.append(link1)
        elif len2 == 2:
            ans.append(link2)
        elif len1 == 4:
            ans.append(link1)
        elif len2 == 4:
            ans.append(link2)
    elif num == 2:
        # 如果申请处理器个数为2，则选择同一链路剩余可用的处理器数量2个的为最佳，其次是剩余4个，最后是剩余3个。
        if len1 == 2:
            ans.append(link1)
        elif len2 == 2:
            ans.append(link2)
        elif len1 == 4:
            ans.append(link1)
        elif len2 == 4:
            ans.append(link2)
        elif len1 == 3:
            ans.append(link1)
        elif len2 == 3:
            ans.append(link2)
    elif num == 4:
        # 如果申请处理器个数为4，则必须选择同一链路剩余可用的处理器数量为4个。
        if len1 == 4:
            ans.append(link1)
        elif len2 == 4:
            ans.append(link2)
    elif num == 8:
        # 如果申请处理器个数为8，则申请节点所有8个处理器。
        if len1 == 4 and len2 == 4:
            # 将两个链路的处理器编号合并到一个列表中。
            tmp = link1 + link2
            ans.append(tmp)
    # 返回符合要求的处理器组合列表。
    return ans
# 从标准输入获取可用处理器编号数组和任务申请的处理器数量。
input_arr = eval(input())
input_num = int(input())
# 调用 get_result 函数并打印结果。
print(get_result(input_arr, input_num))

代码的实现思路如下：

定义一个名为get_result的函数，该函数接受两个参数：arr表示可用处理器编号数组，已排序；num表示任务申请的处理器数量。该函数的返回值是符合要求的处理器组合列表。
在函数内部，首先初始化两个空列表link1和link2，用于存储不同链路中的可用处理器编号。
遍历可用处理器编号数组arr，根据处理器编号是否小于4，将其添加到link1或link2列表中。
初始化一个空列表ans，用于存储符合要求的处理器组合。
计算link1和link2列表的长度，分别表示链路1和链路2中可用的处理器数量。
根据任务申请的处理器数量num进行不同情况的处理：
- 如果num为1，则选择同一链路中剩余可用的处理器数量为1个的最佳，其次是剩余3个的为次佳，然后是剩余2个，最后是剩余4个。
- 如果num为2，则选择同一链路中剩余可用的处理器数量为2个的最佳，其次是剩余4个，最后是剩余3个。
- 如果num为4，则必须选择同一链路中剩余可用的处理器数量为4个。
- 如果num为8，则申请节点所有8个处理器，此时需要将两个链路的处理器编号合并到一个列表中。
在每种情况下，如果找到了符合要求的处理器组合，则将其添加到ans列表中。
函数返回ans列表，即符合要求的处理器组合列表。
在函数外部，从标准输入获取可用处理器编号数组和任务申请的处理器数量，并调用get_result函数，将结果打印出来。

实现三：


class ProcessorScheduler:
    def __init__(self, arr):
        self.arr = arr
        self.link1 = []
        self.link2 = []
        self.ans = []
    def get_result(self, num):
        self.arr.sort()  # 对可用处理器编号数组进行排序
        for e in self.arr:
            if e < 4:
                self.link1.append(e)  # 如果处理器编号小于4，则添加到链路1中
            else:
                self.link2.append(e)  # 如果处理器编号大于等于4，则添加到链路2中
        len1 = len(self.link1)  # 计算链路1中可用的处理器数量
        len2 = len(self.link2)  # 计算链路2中可用的处理器数量
        # 根据任务申请的处理器数量和亲和性调度原则进行处理
        if num == 1:
            # 如果申请处理器个数为1，则选择同一链路，剩余可用的处理器数量为1个的最佳，其次是剩余3个的为次佳，然后是剩余2个，最后是剩余4个。
            if len1 == 1:
                self.dfs(self.link1, 0, 1, [], self.ans)
            elif len2 == 1:
                self.dfs(self.link2, 0, 1, [], self.ans)
            elif len1 == 3:
                self.dfs(self.link1, 0, 1, [], self.ans)
            elif len2 == 3:
                self.dfs(self.link2, 0, 1, [], self.ans)
            elif len1 == 2:
                self.dfs(self.link1, 0, 1, [], self.ans)
            elif len2 == 2:
                self.dfs(self.link2, 0, 1, [], self.ans)
            elif len1 == 4:
                self.dfs(self.link1, 0, 1, [], self.ans)
            elif len2 == 4:
                self.dfs(self.link2, 0, 1, [], self.ans)
        elif num == 2:
            # 如果申请处理器个数为2，则选择同一链路剩余可用的处理器数量2个的为最佳，其次是剩余4个，最后是剩余3个。
            if len1 == 2:
                self.dfs(self.link1, 0, 2, [], self.ans)
            elif len2 == 2:
                self.dfs(self.link2, 0, 2, [], self.ans)
            elif len1 == 4:
                self.dfs(self.link1, 0, 2, [], self.ans)
            elif len2 == 4:
                self.dfs(self.link2, 0, 2, [], self.ans)
            elif len1 == 3:
                self.dfs(self.link1, 0, 2, [], self.ans)
            elif len2 == 3:
                self.dfs(self.link2, 0, 2, [], self.ans)
        elif num == 4:
            # 如果申请处理器个数为4，则必须选择同一链路剩余可用的处理器数量为4个。
            if len1 == 4:
                self.ans.append(self.link1)
            elif len2 == 4:
                self.ans.append(self.link2)
        elif num == 8:
            # 如果申请处理器个数为8，则申请节点所有8个处理器。
            if len1 == 4 and len2 == 4:
                tmp = self.link1 + self.link2  # 将两个链路的处理器编号合并到一个列表中
                self.ans.append(tmp)
        return self.ans
    # 深度优先搜索函数，用于生成符合要求的芯片组合
    def dfs(self, arr, index, level, path, res):
        if len(path) == level:  # 如果路径长度达到要求的处理器数量，则将路径添加到结果列表中
            res.append(path[:])
            return
        for i in range(index, len(arr)):
            path.append(arr[i])  # 将当前处理器编号添加到路径中
            self.dfs(arr, i + 1, level, path, res)  # 递归调用 dfs 函数
            path.pop()  # 回溯，将当前处理器编号从路径中删除
# 输入获取
input_arr = eval(input())
input_num = int(input())
# 算法调用
scheduler = ProcessorScheduler(input_arr)
print(scheduler.get_result(input_num))

代码实现思路如下：

类的定义：ProcessorScheduler

在构造函数中初始化可用处理器编号数组arr，以及用于存储不同链路中可用处理器编号的列表link1和link2，还有用于存储符合要求的处理器组合的列表ans。

方法的定义：get_result

接受一个参数num，表示任务申请的处理器数量。
对可用处理器编号数组arr进行排序。
根据处理器编号将它们划分为两个链路：编号小于4的归为链路1，大于等于4的归为链路2。
根据任务申请的处理器数量和一些预定的规则，使用深度优先搜索函数dfs来生成符合要求的处理器组合，并将结果存储在列表ans中。
返回ans作为结果。

方法的定义：dfs（核心算法）

接受五个参数：arr表示当前链路的可用处理器编号列表，index表示当前搜索的起始位置，level表示任务申请的处理器数量，path表示当前的路径，res表示结果列表。
通过递归的方式，从当前位置开始，依次尝试将每个可用的处理器编号添加到路径中，并继续递归搜索。
如果当前路径的长度达到任务申请的处理器数量，则将该路径添加到结果列表中。
最后，通过回溯的方式，将当前处理器编号从路径中删除，并继续尝试其他可能的组合。

算法调用

从标准输入获取可用处理器编号数组和任务申请的处理器数量。
创建一个ProcessorScheduler类的实例scheduler，并将可用处理器编号数组传递给构造函数。
调用scheduler的get_result方法，并将任务申请的处理器数量传递给它，然后将结果打印出来。

相关阅读:
Trie思想及模板
 大型语言模型的语义搜索(二)：文本嵌入(Text Embeddings)
Linux操作系统资源(持续更新...)
Android 13.0 屏蔽FallbackHome机制去掉android正在启动直接进入默认Launcher功能实现
 VUE3 element-plus源码解析之- 001 dom aria.ts 文件解析
 音频提取：分享几个常用方法，简单好用
 第三方渠道管控，服务商能为您做什么
 FPGA 图像缩放千兆网 UDP 网络视频传输，基于RTL8211 PHY实现，提供工程和QT上位机源码加技术支持
 使用docker部署dubbo项目
 如何将c/c++代码通过NDK交叉工具链移植到Android平台上？
原文地址：https://blog.csdn.net/sxc1414749109/article/details/138135714