当前位置：首页 > news >正文

【华为OD机试真题】任务编排系统 · 双任务时长组合问题（Python/JS）

news 2026/4/14 1:08:56

一、题目描述📝

题目描述：
任务编排服务负责对任务进行组合调度。参与编排的任务有两种类型，其中一种执行时长为taskA，另一种执行时长为taskB。任务一旦开始执行不能被打断，且任务可连续执行。服务每次可以编排num个任务。请编写一个方法，生成每次编排后的任务所有可能的总执行时长。
输入描述：
第1行输入分别为第1种任务执行时长taskA，第2种任务执行时长taskB，这次要编排的任务个数num，以逗号分隔。
输出描述：
数组形式返回所有总执行时时长，需要按从小到大排列。
补充说明:
每种任务的数量都大于本次可以编排的任务数量。
0<taskA
0<taskB
0<=num<=100000
示例1
输入：
1,2,3
输出：
[3, 4, 5, 6]
说明：
可以执行3次taskA，得到结果3，执行2次taskA和次taskB，得到结果4。以此类推，得到最终结果。

二、解题思路深度解析

1. 数学建模：线性方程

设选择任务A的数量为 ii ，则任务B的数量必然为 num−i 。
其中 ii 的取值范围为整数 [0,num]。

总时长 T 的计算公式为：

T(i)=i×taskA+(num−i)×taskB

化简得：

T(i)=i×(taskA−taskB)+num×taskB

2. 核心逻辑

枚举法：由于 i 的取值是连续的整数 0,1,...,num ，我们只需要遍历这 num+1 种情况，计算出对应的 T(i) 即可。
去重问题：
- 若 taskA≠taskB ，则 T(i) 是关于 i 的严格单调函数，所有 num+1个结果互不相同。
- 若 taskA==taskB ，则所有结果都相等，集合中只有一个值。
- 结论：直接计算所有 ii 对应的值，放入列表，然后排序即可 naturally 处理重复（如果有重复值，排序后相邻，题目通常要求列出所有可能值，若理解为“集合”则需去重，但根据示例和常规OD题意，通常指所有组合产生的结果集合。若 taskA=taskBtaskA=taskB ，结果列表应为[X, X, ..., X]还是[X]？
- 修正：题目问的是“所有可能的总执行时长”。如果 A=B=2,num=3 ，无论怎么组合，总时长都是 6。那么“可能的总时长”只有一种情况，即6。
- 关键点：如果 taskA==taskB ，结果应该去重，只保留一个值。如果 taskA≠taskB ，则所有值都不同。
- 通用策略：计算所有值 -> 放入 Set 去重 -> 转 List 排序。这样最稳妥。

3. 算法步骤

解析输入：分割字符串，转为整数。
遍历计算：循环 i 从 0 到 num ，计算 T=i×A+(num−i)×B 。
去重与排序：使用集合（Set）去除重复值（针对 A=B 的情况），然后转换为列表并排序。
格式化输出：按要求输出数组字符串。

4. 复杂度分析

时间复杂度： O(Nlog⁡N) （主要在于排序，若利用单调性可优化至 O(N）。对于 N=105 ，完全可接受。
空间复杂度： O(N) 存储结果。

三、Code实现

1、Python 语言✅️

Python 代码简洁有力，利用set自动去重，sorted轻松排序。

import sys def solve(): # 读取输入 try: line = sys.stdin.readline() if not line: return parts = line.strip().split(',') if len(parts) != 3: return task_a = int(parts[0]) task_b = int(parts[1]) num = int(parts[2]) # 使用集合去重（处理 taskA == taskB 的情况） possible_durations = set() # 遍历 A 的数量 i 从 0 到 num # 优化：直接利用公式计算 for i in range(num + 1): total_time = i * task_a + (num - i) * task_b possible_durations.add(total_time) # 排序 result = sorted(list(possible_durations)) # 格式化输出 [3, 4, 5, 6] # 注意：题目示例中逗号后有空格 print("[" + ", ".join(map(str, result)) + "]") except Exception as e: # 异常处理，防止运行时错误 return if __name__ == "__main__": solve()

💡 Python 代码亮点

自动去重：使用set()存储结果，完美解决 A=B 时结果重复的问题。
简洁排序：sorted()函数直接返回有序列表。
格式化输出：", ".join(map(str, result))快速构建符合要求的字符串。
鲁棒性：加入try-except和输入检查，防止空行或格式错误导致崩溃。

2、JavaScript ✅️

JS 在机考中需注意异步输入处理和数组操作。

const readline = require('readline'); const rl = readline.createInterface({ input: process.stdin, output: process.stdout }); rl.on('line', (line) => { if (!line.trim()) return; const parts = line.split(','); if (parts.length !== 3) return; const taskA = parseInt(parts[0].trim(), 10); const taskB = parseInt(parts[1].trim(), 10); const num = parseInt(parts[2].trim(), 10); // 使用 Set 去重 const durationSet = new Set(); // 遍历计算 for (let i = 0; i <= num; i++) { const total = i * taskA + (num - i) * taskB; durationSet.add(total); } // 转数组并排序 (数字排序需传入比较函数) const result = Array.from(durationSet).sort((a, b) => a - b); // 格式化输出 // JS 的 join 默认逗号无空格，需手动处理或 replace const outputStr = "[" + result.join(", ") + "]"; console.log(outputStr); rl.close(); });

💡 JavaScript 代码亮点

Set 数据结构：ES6 的Set天然去重，逻辑清晰。
数字排序陷阱：JS 默认的sort()是按字典序（字符串）排序的（如10会排在2前面）。必须传入(a, b) => a - b进行数值排序。
输入处理：使用readline模块标准处理单行输入，trim()去除潜在空格。
输出格式：join(", ")确保逗号后有空格，符合题目示例格式。

五、进阶优化：利用单调性 ( O(N) )🔍

虽然排序很快，但如果我们想展示更强的算法功底，可以利用数学性质免去排序和去重步骤。

推导：
T(i)=i×(A−B)+num×B

情况 1： A>B
- 系数 (A−B)>0 ，函数单调递增。
- ii 从 0→num ，结果天然升序。
- 结果数量：若 A≠B ，有 num+1 个；若 A=B ，有 1 个。
情况 2： A<B
- 系数 (A−B)<0( ，函数单调递减。
- ii 从 0→num ，结果降序。
- 策略：让 i 从 num→0 遍历，结果即天然升序。
情况 3： A=B
- 结果恒为 num×A 。
- 策略：直接输出[num * A]。

优化后的 Python 逻辑片段：

result = [] if task_a == task_b: result = [num * task_a] elif task_a > task_b: # A > B, i 增大，总值增大。正序遍历 0->num for i in range(num + 1): result.append(i * task_a + (num - i) * task_b) else: # A < B, i 增大，总值减小。倒序遍历 num->0 以获得升序 for i in range(num, -1, -1): result.append(i * task_a + (num - i) * task_b) # 此时 result 已经是有序且无重复的，无需 sort 和 set

注：这种写法将复杂度严格降低到 O(N) ，在 N 极大时优势明显，是面试中的加分项。

六、避坑指南⚠️

数字排序误区 (JS)：
- ❌ 错误：[10, 2].sort()结果是[10, 2]。
- ✅ 正确：[10, 2].sort((a, b) => a - b)结果是[2, 10]。
去重逻辑：
- 很多同学忽略 A=B 的情况，输出了[6, 6, 6, 6]。题目问的是“可能的总时长”，语义上指值的集合，应去重为[6]。使用Set是最安全的做法。
输出格式细节：
- 仔细观察示例[3, 4, 5, 6]，逗号后面有一个空格。
- Python:", ".join(...)
- JS:join(", ")
- 漏掉空格可能导致格式校验失败。
大数溢出：
- 虽然 Python 和 JS (ES2020+) 对大数支持较好，但在极端情况下（ num=105,task=109 ），结果达 1014 。
- Python 自动处理大整数，无需担心。
- JS 中 1014 仍在Number(双精度浮点) 的安全整数范围 (253≈9×1015 ) 内，无需BigInt，但需注意精度问题（本题纯整数运算，安全）。