(A卷,100分)- 处理器问题（Java JS Python）题目描述

题目描述

某公司研发了一款高性能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. 任务申请的处理器数量只能是1、2、4、8。
2. 编号0-3的处理器处于一个链路，编号4-7的处理器处于另外一个链路。
3. 处理器编号唯一，且不存在相同编号处理器。

输入描述

输入包含可用的处理器编号数组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. 贪心算法（Greedy Algorithm）：题目中明确规定了不同申请数量下的优先级顺序，需要按照优先级依次选择最优链路
2. 组合搜索（Combinatorial Search）：从选定的链路中选择指定数量的处理器组合
3. 条件分支逻辑：根据不同的申请数量应用不同的选择规则

基础知识点

1. 数组分组与过滤：将处理器按链路分组（0-3和4-7两组）
2. 排序与组合生成：对结果进行排序和组合生成
3. 边界条件处理：处理特殊情况如申请8个处理器或无可用处理器的情况

版本1：纯贪心算法（推荐⭐）

适用场景：只需要返回一个符合条件的分配方案（最符合实际调度场景）

const rl = require("readline").createInterface({ input: process.stdin }); const iter = rl[Symbol.asyncIterator](); const readline = async () => (await iter.next()).value; void async function() { // 读取输入 let line1 = await readline(); if (!line1) return; const array = JSON.parse(line1.trim()); let line2 = await readline(); if (!line2) return; const num = parseInt(line2.trim()); // 1. 分组逻辑：链路A(0-3), 链路B(4-7) const linkA = array.filter(v => v >= 0 && v <= 3).sort((a, b) => a - b); const linkB = array.filter(v => v >= 4 && v <= 7).sort((a, b) => a - b); // 2. 特殊情况：申请8个处理器 if (num === 8) { if (array.length === 8) { console.log(JSON.stringify([array.sort((a, b) => a - b)])); } else { console.log("[]"); } rl.close(); return; } // 3. 亲和性调度优先级定义 const priorityMap = { 1: [1, 3, 2, 4], // 申请1个：优先选剩余1个的链路，其次3、2、4 2: [2, 4, 3], // 申请2个：优先选剩余2个的链路，其次4、3 4: [4] // 申请4个：必须选剩余4个的链路 }; const priorities = priorityMap[num]; if (!priorities) { console.log("[]"); rl.close(); return; } // 4. 贪心算法：按优先级查找最优链路 for (let targetLen of priorities) { // 检查链路A是否符合条件 if (linkA.length === targetLen) { console.log(JSON.stringify([linkA.slice(0, num)])); rl.close(); return; } // 检查链路B是否符合条件 if (linkB.length === targetLen) { console.log(JSON.stringify([linkB.slice(0, num)])); rl.close(); return; } } // 5. 未找到符合条件的链路 console.log("[]"); rl.close(); }();

优势：

• ✅ 时间复杂度：O(n)
• ✅ 空间复杂度：O(1)
• ✅ 代码简洁，逻辑清晰
• ✅ 符合实际资源调度场景

版本2：贪心 + 优化组合生成（如果需要返回所有组合）

适用场景：题目明确要求返回所有可能的组合方案

const rl = require("readline").createInterface({ input: process.stdin }); const iter = rl[Symbol.asyncIterator](); const readline = async () => (await iter.next()).value; /** * 优化的组合生成函数（针对本题特点） */ function getCombinations(arr, k) { // 特殊情况优化 if (k === 1) { return arr.map(x => [x]); } if (k === arr.length) { return [arr]; } if (k === 2 && arr.length === 4) { // 针对 num=2, 链路剩余4个的情况优化 const result = []; for (let i = 0; i < arr.length - 1; i++) { for (let j = i + 1; j < arr.length; j++) { result.push([arr[i], arr[j]]); } } return result; } // 通用回溯算法 const result = []; const backtrack = (start, current) => { if (current.length === k) { result.push([...current]); return; } for (let i = start; i < arr.length; i++) { current.push(arr[i]); backtrack(i + 1, current); current.pop(); } }; backtrack(0, []); return result; } void async function() { // 读取输入 let line1 = await readline(); if (!line1) return; const array = JSON.parse(line1.trim()); let line2 = await readline(); if (!line2) return; const num = parseInt(line2.trim()); // 1. 分组逻辑：链路A(0-3), 链路B(4-7) const linkA = array.filter(v => v >= 0 && v <= 3).sort((a, b) => a - b); const linkB = array.filter(v => v >= 4 && v <= 7).sort((a, b) => a - b); // 2. 特殊情况：申请8个处理器 if (num === 8) { if (array.length === 8) { console.log(JSON.stringify([array.sort((a, b) => a - b)])); } else { console.log("[]"); } rl.close(); return; } // 3. 亲和性调度优先级定义 const priorityMap = { 1: [1, 3, 2, 4], 2: [2, 4, 3], 4: [4] }; const priorities = priorityMap[num]; if (!priorities) { console.log("[]"); rl.close(); return; } // 4. 贪心算法：按优先级查找最优链路 for (let targetLen of priorities) { const matchedLinks = []; if (linkA.length === targetLen) matchedLinks.push(linkA); if (linkB.length === targetLen) matchedLinks.push(linkB); // 找到符合当前优先级的链路 if (matchedLinks.length > 0) { const result = []; for (let link of matchedLinks) { const combinations = getCombinations(link, num); result.push(...combinations); } console.log(JSON.stringify(result)); rl.close(); return; } } // 5. 未找到符合条件的链路 console.log("[]"); rl.close(); }();

优化点：

• ✅ 针对常见情况（k=1, k=arr.length）做了特殊优化
• ✅ 保留了回溯算法的通用性
• ✅ 代码结构更清晰

版本3：极致优化（针对题目特点）

适用场景：深度优化，针对本题的特殊约束

const rl = require("readline").createInterface({ input: process.stdin }); const iter = rl[Symbol.asyncIterator](); const readline = async () => (await iter.next()).value; /** * 针对本题优化的组合生成 * 由于链路最多4个处理器，可以直接枚举 */ function getOptimizedCombinations(arr, k) { const n = arr.length; if (k === 1) { return arr.map(x => [x]); } if (k === n) { return [arr]; } if (k === 2) { const result = []; for (let i = 0; i < n - 1; i++) { for (let j = i + 1; j < n; j++) { result.push([arr[i], arr[j]]); } } return result; } // k=4 且 n=4 的情况 if (k === 4 && n === 4) { return [arr]; } return []; } void async function() { try { // 读取输入 let line1 = await readline(); if (!line1) return; const array = JSON.parse(line1.trim()); let line2 = await readline(); if (!line2) return; const num = parseInt(line2.trim()); // 1. 分组逻辑 const linkA = array.filter(v => v >= 0 && v <= 3).sort((a, b) => a - b); const linkB = array.filter(v => v >= 4 && v <= 7).sort((a, b) => a - b); // 2. 特殊情况：申请8个 if (num === 8) { console.log(array.length === 8 ? JSON.stringify([array.sort((a, b) => a - b)]) : "[]"); rl.close(); return; } // 3. 亲和性调度优先级 const priorityMap = { 1: [1, 3, 2, 4], 2: [2, 4, 3], 4: [4] }; const priorities = priorityMap[num]; if (!priorities) { console.log("[]"); rl.close(); return; } // 4. 贪心查找 for (let targetLen of priorities) { const result = []; if (linkA.length === targetLen) { result.push(...getOptimizedCombinations(linkA, num)); } if (linkB.length === targetLen) { result.push(...getOptimizedCombinations(linkB, num)); } if (result.length > 0) { console.log(JSON.stringify(result)); rl.close(); return; } } console.log("[]"); } catch (error) { console.log("[]"); } finally { rl.close(); } }();

三个版本对比

我的建议

如果是实际生产环境或OJ判题：推荐版本1（纯贪心）

• 最符合调度系统的实际需求
• 性能最优
• 代码最简洁

如果题目明确要求返回所有组合：推荐版本3（极致优化）

• 针对题目特点深度优化
• 避免了回溯的递归开销
• 性能优于通用回溯

代码解析

1. 输入处理：使用readline模块读取输入，解析可用处理器数组和申请数量
2. 特殊情况处理：当申请8个处理器时，直接检查数组长度是否为8
3. 链路分组：将处理器分为0-3和4-7两个链路组
4. 优先级处理：根据申请数量应用不同的优先级规则
5. 组合生成：使用回溯法生成指定数量的处理器组合
6. 结果输出：按照优先级找到最佳链路后生成并输出所有可能的组合

该算法的时间复杂度取决于组合生成的数量，在最坏情况下为O(C(n,k))，其中n是链路中的处理器数量，k是申请的处理器数量。由于处理器总数最多为8，所以算法效率很高。