华为OD机考任务编排系统算法解析与Java实现
1. 任务编排系统问题解析
最近在准备华为OD机考时遇到一个挺有意思的算法题——任务编排系统。这个问题看似简单，但想要高效解决还是需要动些脑筋的。我花了几天时间研究这个问题，把解题思路和Java实现整理出来分享给大家。
1.1 问题本质理解
这个问题本质上是一个组合数学问题。我们有两种任务：
- 任务A：执行时长为taskA
- 任务B：执行时长为taskB
每次需要编排num个任务，这些任务可以是A或B的任意组合。我们需要计算出所有可能的总执行时长，并按从小到大排序输出。
举个例子，如果taskA=1，taskB=2，num=3，那么可能的组合有：
- 3个A：1+1+1=3
- 2个A和1个B：1+1+2=4
- 1个A和2个B：1+2+2=5
- 3个B：2+2+2=6
所以最终输出应该是[3,4,5,6]。
1.2 关键约束条件
题目给出了几个重要约束：
- 任务一旦开始执行不能被打断
- 任务可以连续执行
- 0 < taskA
- 0 < taskB
- 0 <= num <= 100000
特别注意num的范围可以很大（最大10万），这意味着我们需要一个高效的算法，不能简单地枚举所有组合。
2. 解题思路分析
2.1 暴力枚举法的局限性
最直观的想法是枚举所有可能的组合。对于num个任务，每个任务有2种选择（A或B），所以总共有2^num种组合。当num较大时（比如num=100），这显然不可行。
2.2 数学优化思路
其实我们不需要枚举所有组合，因为最终只关心总时长，而不同组合可能产生相同的总时长。总时长的计算公式为：
总时长 = k × taskA + (num - k) × taskB
其中k是A任务的数量，取值范围是0 ≤ k ≤ num。
因此，我们只需要遍历k从0到num，计算对应的总时长即可。这样时间复杂度就从O(2^num)降到了O(num)，对于num=100000也能高效处理。
2.3 去重与排序
由于taskA和taskB可能相等，或者存在不同的k值产生相同的总时长，我们需要：
- 使用Set来存储结果以自动去重
- 最后将结果转换为List并排序
3. Java实现详解
3.1 输入处理
首先我们需要处理输入，输入是以逗号分隔的三个数字：
import java.util.*; public class TaskScheduler { public static void main(String[] args) { Scanner scanner = new Scanner(System.in); String[] inputs = scanner.nextLine().split(","); int taskA = Integer.parseInt(inputs[0]); int taskB = Integer.parseInt(inputs[1]); int num = Integer.parseInt(inputs[2]); List<Integer> result = calculateDurations(taskA, taskB, num); System.out.println(result); } }3.2 核心算法实现
public static List<Integer> calculateDurations(int taskA, int taskB, int num) { Set<Integer> durations = new HashSet<>(); for (int k = 0; k <= num; k++) { int total = k * taskA + (num - k) * taskB; durations.add(total); } List<Integer> result = new ArrayList<>(durations); Collections.sort(result); return result; }3.3 算法优化
虽然上述代码已经足够高效，但当num很大时（接近10万），我们可以做进一步优化：
- 如果taskA == taskB，那么所有组合的总时长都相同，可以直接返回[num*taskA]
- 使用TreeSet代替HashSet+排序，可以自动维护有序集合
优化后的代码：
public static List<Integer> calculateDurationsOptimized(int taskA, int taskB, int num) { if (taskA == taskB) { return Collections.singletonList(num * taskA); } Set<Integer> durations = new TreeSet<>(); for (int k = 0; k <= num; k++) { int total = k * taskA + (num - k) * taskB; durations.add(total); } return new ArrayList<>(durations); }4. 复杂度分析与边界情况
4.1 时间复杂度
- 最优情况（taskA == taskB）：O(1)
- 一般情况：O(num)，因为需要遍历0到num
- 转换为有序列表：O(n log n)，其中n是不同总时长的数量（n ≤ num+1）
4.2 空间复杂度
- 最坏情况下需要存储num+1个不同的总时长：O(num)
4.3 边界情况处理
- num=0：应该返回空列表，因为无法编排0个任务
- taskA或taskB为0：根据题目约束，这种情况不会出现
- num很大（如10万）：我们的算法仍然可以高效处理
修改后的代码应加入对num=0的处理：
public static List<Integer> calculateDurationsOptimized(int taskA, int taskB, int num) { if (num == 0) { return Collections.emptyList(); } if (taskA == taskB) { return Collections.singletonList(num * taskA); } Set<Integer> durations = new TreeSet<>(); // 其余代码不变 ... }5. 测试用例验证
让我们用几个测试用例来验证我们的解决方案：
5.1 示例测试
输入：1,2,3 预期输出：[3,4,5,6] 实际输出一致。
5.2 相等时长测试
输入：2,2,5 预期输出：[10] 实际输出一致。
5.3 大数测试
输入：100,200,100000 预期输出：应包含从100×100000到200×100000的所有100的倍数的数 实际输出正确。
5.4 边界测试
输入：1,1,0 预期输出：[] 实际输出一致。
6. 算法扩展思考
这个问题可以有几种变体值得思考：
如果任务类型不止两种，而是多种，该如何解决？
- 这时问题会变成多维的组合问题，可能需要使用动态规划
如果每个任务有多个属性（如时长和优先级），需要优化多个目标，该如何处理？
- 这可能变成一个多目标优化问题
如果任务之间有依赖关系，不能任意组合，该如何建模？
- 这会变成一个更复杂的调度问题，可能需要图论知识
7. 实际应用场景
这类任务编排问题在实际系统中有广泛应用：
- 分布式任务调度：分配不同性能的节点处理任务
- 资源分配：将不同类型的资源分配给多个任务
- 批处理系统：合理安排不同耗时的批处理作业
理解这类基础算法问题，有助于我们设计更复杂的分布式系统。
8. 编码风格建议
在解决这类算法问题时，建议：
- 先写清楚思路注释，再写代码
- 处理好边界情况
- 使用有意义的变量名（如用k表示A任务的数量）
- 添加必要的单元测试
- 考虑性能优化空间
9. 常见错误与调试技巧
在实现这个算法时，容易犯的错误包括：
- 忘记处理taskA == taskB的特殊情况
- 没有考虑num=0的边界情况
- 使用List而不是Set导致重复元素
- 排序时使用了不稳定的排序算法
调试技巧：
- 先用小规模数据测试
- 打印中间结果验证
- 对比暴力解法的结果（当num较小时）
10. 性能优化进阶
对于特别大的num（如10^9级），我们还可以进一步优化：
- 观察到总时长是线性变化的，可以只记录最小和最大值，以及步长
- 使用数学方法直接计算不同总时长的数量，而不需要遍历
例如，如果taskA=2，taskB=3，num=100000，那么：
- 最小总时长：全部选A，2×100000=200000
- 最大总时长：全部选B，3×100000=300000
- 步长：gcd(taskA,taskB)=1，所以总时长覆盖200000到300000的所有整数
优化后的算法：
public static List<Integer> calculateDurationsMath(int taskA, int taskB, int num) { if (num == 0) return Collections.emptyList(); if (taskA == taskB) return Collections.singletonList(num * taskA); int gcd = gcd(taskA, taskB); int min = Math.min(taskA, taskB); int max = Math.max(taskA, taskB); int start = num * min; int end = num * max; int step = (taskA == min) ? (max - min) : (min - max); step = Math.abs(step) / gcd; List<Integer> result = new ArrayList<>(); for (int i = start; i <= end; i += step) { result.add(i); } return result; } private static int gcd(int a, int b) { return b == 0 ? a : gcd(b, a % b); }这个优化将时间复杂度从O(num)降低到了O(num×gcd(taskA,taskB))，对于特别大的num更高效。
11. 不同语言实现对比
虽然题目要求Java实现，但了解其他语言的实现也有助于理解算法本质：
11.1 Python实现
def calculate_durations(taskA, taskB, num): if num == 0: return [] if taskA == taskB: return [taskA * num] return sorted({k * taskA + (num - k) * taskB for k in range(num + 1)})Python的实现非常简洁，利用了集合推导式和内置排序。
11.2 C++实现
#include <vector> #include <set> #include <algorithm> std::vector<int> calculateDurations(int taskA, int taskB, int num) { if (num == 0) return {}; if (taskA == taskB) return {taskA * num}; std::set<int> durations; for (int k = 0; k <= num; ++k) { durations.insert(k * taskA + (num - k) * taskB); } return std::vector<int>(durations.begin(), durations.end()); }C++实现利用了STL的set来自动排序和去重。
12. 在线评测注意事项
在华为OD的在线评测系统中提交代码时，需要注意：
- 类名必须为Main
- 使用标准输入输出
- 不要添加额外的包或打印调试信息
- 注意处理输入输出的格式要求
正确的提交格式：
import java.util.*; public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); String[] inputs = sc.nextLine().split(","); int taskA = Integer.parseInt(inputs[0]); int taskB = Integer.parseInt(inputs[1]); int num = Integer.parseInt(inputs[2]); List<Integer> res = calculateDurations(taskA, taskB, num); System.out.println(res); } // 包含之前实现的calculateDurations方法 ... }13. 算法选择总结
对于这个问题，我们经历了几个思考阶段：
- 暴力枚举法：不可行，时间复杂度高
- 数学遍历法：O(num)时间复杂度，适用于一般情况
- 数学优化法：利用GCD进一步优化，适用于极大num
在实际编程中，应根据具体场景选择合适的实现。对于机考题目，第二种方法通常足够，因为它实现简单且对一般测试用例效率足够。
14. 学习资源推荐
如果想进一步学习这类算法问题，推荐以下资源：
- 《算法导论》中的组合数学章节
- LeetCode上的类似问题（如Coin Change）
- 组合数学在线课程
- 华为OD往年真题集
15. 个人解题心得
在解决这个问题的过程中，我总结了几个经验：
- 不要被问题的表面描述迷惑，要深入分析其数学本质
- 先考虑小规模例子，再推广到一般情况
- 注意题目中的约束条件，它们往往是优化算法的关键
- 编写代码前先写好伪代码或思路注释
- 边界情况测试不可忽视
这个题目很好地展示了如何将一个看似复杂的实际问题抽象为简单的数学模型，这也是算法问题解决的魅力所在。
