思路

为了根据亲和性调度原则选择合适的处理器组合，需按照以下步骤进行：

1. 链路划分

将可用的处理器编号 array 分为两个独立的链路：

• 链路1：编号 0-3
• 链路2：编号 4-7

这样可以确保不同链路的处理器之间不会混合选择，从而满足不通链路的通信限制。

2. 统计可用处理器数量

分别统计每个链路中可用的处理器数量：

• 链路1 的可用处理器数量 count1
• 链路2 的可用处理器数量 count2

3. 确定优先级顺序

根据任务申请的处理器数量 num，确定优先级顺序。优先级列表按照从高到低的优先级排列，具体如下：

• num = 1 时：
  • 优先级顺序为 [1, 3, 2, 4]
• num = 2 时：
  • 优先级顺序为 [2, 4, 3]
• num = 4 时：
  • 优先级顺序为 [4]
• num = 8 时：
  • 必须选择所有 8 颗处理器

4. 选择符合最高优先级的链路

按照确定的优先级顺序，依次检查每个优先级值，选择所有符合当前优先级的链路：

1. 遍历优先级列表：

   • 对于每个优先级值 p，检查链路1和链路2的可用处理器数量是否等于 p。

2. 记录符合条件的链路：

   • 如果链路1的可用数量 count1 == p，则将链路1加入候选链路集合。
   • 如果链路2的可用数量 count2 == p，则将链路2加入候选链路集合。

3. 一旦找到符合当前优先级的链路，立即停止进一步的优先级检查，确保只选择最高优先级的链路。

5. 生成处理器组合

对于所有选定的候选链路，生成所有可能的处理器组合：

1. 遍历每个候选链路：

   • 对于每个候选链路，从其可用处理器中选择 num 个处理器的所有可能组合。

2. 组合生成方法：

   • 使用递归回溯、迭代或内置组合生成函数（如 C++ 的 backtrack、Python 的 itertools.combinations、Java 的递归方法）生成所有可能的组合。

3. 合并所有链路的组合：

   • 将来自不同链路的所有组合合并到一个最终的结果列表中。

6. 处理特殊情况

根据不同的 num 值，处理一些特殊情况：

• num = 8 时：

  • 检查所有 8 颗处理器是否都可用。
  • 如果是，则返回所有处理器的组合。
  • 否则，返回空列表。

• 不可满足的情况：

  • 如果在所有优先级检查后，没有找到任何符合条件的链路，则返回空列表。

7. 确保结果的正确性

为了保证结果的正确性和一致性，执行以下操作：

1. 排序处理器编号：

   • 对每个组合中的处理器编号进行排序，确保组合内的顺序一致。

2. 排序所有组合：

   • 对所有生成的组合进行排序，确保输出顺序的一致性，便于比较和测试。

3. 去重（如有必要）：

   • 确保结果列表中没有重复的组合。

8. 输出结果

根据生成的组合列表，按照题目要求的格式输出结果：

• 存在符合条件的组合：

  • 输出包含所有符合条件的处理器组合的列表。

• 不存在符合条件的组合：

  • 输出空列表 []。

cpp

#include <bits/stdc++.h>
using namespace std;

// 函数用于生成组合
vector<vector<int>> generateCombinations(const vector<int> &processors, int num) {
    vector<vector<int>> result;
    int n = processors.size();
    if (num > n) return result;

    vector<int> combination;
    // 递归生成所有可能的组合
    function<void(int)> backtrack = [&](int start) {
        if (combination.size() == num) {
            result.emplace_back(combination);
            return;
        }
        for (int i = start; i < n; ++i) {
            combination.push_back(processors[i]);
            backtrack(i + 1);
            combination.pop_back();
        }
    };
    backtrack(0);
    return result;
}

int main(){
    // 读取输入
    string s;
    getline(cin, s);
    // 解析数组
    vector<int> array;
    int num;
    // Remove brackets
    if (s.size() >= 2) s = s.substr(1, s.size()-2);
    else s = "";
    // Split by comma
    stringstream ss(s);
    string item;
    while(getline(ss, item, ',')){
        // Remove possible spaces
        item.erase(remove(item.begin(), item.end(), ' '), item.end());
        if(!item.empty())
            array.push_back(stoi(item));
    }
    cin >> num;

    // 分别划分到两个链路
    vector<int> link1, link2;
    for(auto p : array){
        if(p >=0 && p <=3)
            link1.push_back(p);
        else if(p >=4 && p <=7)
            link2.push_back(p);
    }

    // 定义优先级
    vector<int> priorities;
    if(num ==1){
        priorities = {1,3,2,4};
    }
    else if(num ==2){
        priorities = {2,4,3};
    }
    else if(num ==4){
        priorities = {4};
    }
    else if(num ==8){
        // 必须所有8个处理器都可用
        if(array.size() ==8){
            vector<int> sorted_array = array;
            sort(sorted_array.begin(), sorted_array.end());
            // 打印结果
            cout << "[[";
            for(int i=0;i<sorted_array.size(); ++i){
                cout << sorted_array[i];
                if(i != sorted_array.size()-1) cout << ", ";
            }
            cout << "]]";
            return 0;
        }
        else{
            // 返回空列表
            cout << "[]";
            return 0;
        }
    }
    else{
        // 无效的num
        cout << "[]";
        return 0;
    }

    // 按优先级选择所有符合当前最高优先级的链路
    vector<vector<int>> selected_links;
    for(auto p : priorities){
        // 找到所有链路中剩余数量为p的链路
        vector<int> current_links;
        if(link1.size() == p)
            current_links.push_back(1); // 标识为链路1
        if(link2.size() == p)
            current_links.push_back(2); // 标识为链路2
        if(!current_links.empty()){
            // 根据标识选择对应的链路
            for(auto id : current_links){
                if(id ==1)
                    selected_links.emplace_back(link1);
                else if(id ==2)
                    selected_links.emplace_back(link2);
            }
            break; // 只选择最高优先级的链路
        }
    }

    if(selected_links.empty()){
        // 无符合条件的链路
        cout << "[]";
        return 0;
    }

    // 生成所有符合条件的组合
    vector<vector<int>> combinations;
    for(auto &link : selected_links){
        vector<vector<int>> comb = generateCombinations(link, num);
        combinations.insert(combinations.end(), comb.begin(), comb.end());
    }

    if(combinations.empty()){
        cout << "[]";
        return 0;
    }

    // 排序组合中的元素
    for(auto &comb : combinations){
        sort(comb.begin(), comb.end());
    }

    // 排序所有组合以保证输出顺序一致
    sort(combinations.begin(), combinations.end());

    // 打印结果
    cout << "[";
    for(int i=0;i<combinations.size(); ++i){
        cout << "[";
        for(int j=0; j<combinations[i].size(); ++j){
            cout << combinations[i][j];
            if(j != combinations[i].size()-1) cout << ", ";
        }
        cout << "]";
        if(i != combinations.size()-1) cout << ", ";
    }
    cout << "]";
    return 0;
}

python

import sys
import itertools

def main():
    import sys
    import ast
    # 读取输入
    lines = sys.stdin.read().splitlines()
    if not lines:
        print("[]")
        return
    array_str = lines[0].strip()
    if len(lines) <2:
        print("[]")
        return
    num_str = lines[1].strip()
    try:
        array = ast.literal_eval(array_str)
        num = int(num_str)
    except:
        print("[]")
        return
    # 划分链路
    link1 = [p for p in array if 0 <= p <=3]
    link2 = [p for p in array if 4 <= p <=7]
    # 定义优先级
    if num ==1:
        priorities = [1,3,2,4]
    elif num ==2:
        priorities = [2,4,3]
    elif num ==4:
        priorities = [4]
    elif num ==8:
        if len(array)==8:
            sorted_array = sorted(array)
            print([sorted_array])
        else:
            print([])
        return
    else:
        print([])
        return
    # 按优先级选择所有符合当前最高优先级的链路
    selected_links = []
    for p in priorities:
        current_links = []
        if len(link1) == p:
            current_links.append(link1)
        if len(link2) == p:
            current_links.append(link2)
        if current_links:
            selected_links.extend(current_links)
            break  # 只选择最高优先级的链路
    if not selected_links:
        print([])
        return
    # 生成组合
    combinations = []
    for link in selected_links:
        if len(link) >= num:
            comb = list(itertools.combinations(sorted(link), num))
            combinations.extend([list(c) for c in comb])
    if not combinations:
        print([])
        return
    print(combinations)

if __name__ == "__main__":
    main()

java

import java.util.*;
import java.io.*;

public class Main {
    // 生成组合
    public static List<List<Integer>> generateCombinations(List<Integer> processors, int num){
        List<List<Integer>> result = new ArrayList<>();
        backtrack(processors, num, 0, new ArrayList<>(), result);
        return result;
    }

    private static void backtrack(List<Integer> processors, int num, int start, List<Integer> temp, List<List<Integer>> result){
        if(temp.size() == num){
            result.add(new ArrayList<>(temp));
            return;
        }
        for(int i=start; i<processors.size(); i++){
            temp.add(processors.get(i));
            backtrack(processors, num, i+1, temp, result);
            temp.remove(temp.size()-1);
        }
    }

    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String arrayStr = br.readLine();
        String numStr = br.readLine();
        // 解析数组
        arrayStr = arrayStr.substring(1, arrayStr.length()-1);
        String[] parts = arrayStr.split(",");
        List<Integer> array = new ArrayList<>();
        for(String part: parts){
            part = part.trim();
            if(!part.isEmpty()){
                array.add(Integer.parseInt(part));
            }
        }
        int num = Integer.parseInt(numStr);
        // 划分链路
        List<Integer> link1 = new ArrayList<>();
        List<Integer> link2 = new ArrayList<>();
        for(int p : array){
            if(p >=0 && p <=3)
                link1.add(p);
            else if(p >=4 && p <=7)
                link2.add(p);
        }
        // 定义优先级
        List<Integer> priorities = new ArrayList<>();
        if(num ==1){
            priorities = Arrays.asList(1,3,2,4);
        }
        else if(num ==2){
            priorities = Arrays.asList(2,4,3);
        }
        else if(num ==4){
            priorities = Arrays.asList(4);
        }
        else if(num ==8){
            if(array.size() ==8){
                List<Integer> sorted = new ArrayList<>(array);
                Collections.sort(sorted);
                System.out.println("[" + sorted + "]");
            }
            else{
                System.out.println("[]");
            }
            return;
        }
        else{
            System.out.println("[]");
            return;
        }
        // 按优先级选择所有符合当前最高优先级的链路
        List<List<Integer>> selected_links = new ArrayList<>();
        for(int p : priorities){
            List<List<Integer>> current_links = new ArrayList<>();
            if(link1.size() == p){
                current_links.add(link1);
            }
            if(link2.size() == p){
                current_links.add(link2);
            }
            if(!current_links.isEmpty()){
                selected_links.addAll(current_links);
                break; // 只选择最高优先级的链路
            }
        }
        if(selected_links.isEmpty()){
            System.out.println("[]");
            return;
        }
        // 生成组合
        List<List<Integer>> combinations = new ArrayList<>();
        for(List<Integer> link : selected_links){
            if(link.size() >= num){
                combinations.addAll(generateCombinations(link, num));
            }
        }
        if(combinations.isEmpty()){
            System.out.println("[]");
            return;
        }
        // 排序组合中的元素
        for(List<Integer> comb : combinations){
            Collections.sort(comb);
        }
        // 排序所有组合
        combinations.sort((a, b) -> {
            for(int i=0; i< Math.min(a.size(), b.size()); i++){
                if(!a.get(i).equals(b.get(i))){
                    return a.get(i) - b.get(i);
                }
            }
            return a.size() - b.size();
        });
        // 打印结果
        StringBuilder sb = new StringBuilder();
        sb.append("[");
        for(int i=0; i<combinations.size(); i++){
            sb.append("[");
            for(int j=0; j<combinations.get(i).size(); j++){
                sb.append(combinations.get(i).get(j));
                if(j != combinations.get(i).size()-1) sb.append(", ");
            }
            sb.append("]");
            if(i != combinations.size()-1) sb.append(", ");
        }
        sb.append("]");
        System.out.println(sb.toString());
    }
}

题目内容

某公司研发了一款高性能 $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]]$。

样例1

输入

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

输出

[[0], [1]]

说明

根据第一条亲和性调度原则，在剩余两个处理器的链路$（0, 1, 2, 3）$中选择处理器。

由于只有 $0$ 和 $1$ 可用，则返回任意一颗处理器即可。

样例2

输入

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

输出

[[4, 5, 6, 7]]

说明

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