一、题目描述

某公司研发了一款高性能AI处理器。每台物理设备具备8颗AI处理器，编号分别为0、1、2、3、4、5、6、7。编号0-3的处理器处于同一个链路中，编号4-7的处理器处于另外一个链路中，不通链路中的处理器不能通信。如下图所示：

现给定服务器可用的处理器编号数组array，以及任务申请的处理器数量num，找出符合下列亲和性调度原则的芯片组合。如果不存在符合要求的组合，则返回空列表。

亲和性调度原则：

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

提示：

1. 任务申请的处理器数量只能是1、2、4、8。
2. 编号0-3的处理器处于一个链路，编号4-7的处理器处于另外一个链路。
3. 处理器编号唯一，且不存在相同编号处理器。

二、输入输出描述

输入描述

• 第一行：可用处理器编号数组array；
• 第二行：任务申请的处理器数量num。

输出描述

• 符合规则的处理器编号组合列表，无则返回空列表。

三、示例

四、解题思路

1. 核心思想

1. 核心思想

先按处理器编号特征（是否≥4）分组，再针对不同调度级别执行差异化的组合生成规则：低级别（1/2）生成任意指定数量的组合，高级别（4/8）仅匹配固定数量的分组 / 合并结果 —— 核心是 “分组分类 + 规则化生成组合”。

2. 问题本质分析

• 表层问题：根据调度级别，从处理器数组中筛选符合数量 / 分组规则的组合列表；
• 深层问题：
  1. 数据分类：按编号特征将处理器拆分为两个独立分组，满足调度的分组约束；
  2. 组合生成：低级别需枚举所有 “选 k 个” 的组合（回溯法），高级别仅匹配固定数量的分组 / 合并结果（无需枚举）；
  3. 规则匹配：不同调度级别对应不同的组合生成逻辑，需精准匹配数量约束。

3. 核心逻辑

• 分组前置：将处理器按编号 < 4/≥4 拆分为link1/link2，为后续规则匹配奠定基础；
• 规则分支：
  • 级别 1/2：通过回溯法枚举两组中 “选 num 个” 的所有组合（保证不重复、不遗漏）；
  • 级别 4：仅匹配 “单组恰好 4 个元素” 的情况，直接取整组为组合；
  • 级别 8：仅匹配 “两组各 4 个元素” 的情况，合并两组为一个组合；
• 结果聚合：将不同规则下生成的组合汇总，返回最终列表。

4. 步骤拆解

1. 输入解析与预处理：

   • 解析带格式的处理器数组（去除括号、逗号、空格），转换为整数数组；
   • 读取调度级别num。

2. 处理器分组：

   • 遍历数组，将编号 < 4 的归入link1，≥4 的归入link2。

3. 按调度级别生成组合：

   • 级别 1/2：对link1/link2分别调用回溯法，生成所有 “选 num 个” 的组合；
   • 级别 4：检查link1/link2是否恰好有 4 个元素，有则加入结果；
   • 级别 8：检查link1和link2是否各有 4 个元素，是则合并两组加入结果。

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 数组
        // 读取调度级别 num
        int 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);  // 回溯，移除最后一个元素
        }
    }
}