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

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

news 2026/5/12 0:12:20

一、题目描述📝

题目描述：
任务编排服务负责对任务进行组合调度。参与编排的任务有两种类型，其中一种执行时长为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的数量为 i ，则任务B的数量为 num−ii ，其中 0≤i≤num 。
总时长 T(i)的公式为：

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

整理得：

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

这是一个关于 i 的一次函数。

2. 单调性分析（核心优化点）

C语言没有内置的动态数组或自动排序容器，因此利用数学性质直接生成有序数据至关重要。

情况 1： taskA>taskB
- 斜率 >0 ，函数单调递增。
- 策略：让 i 从 0 遍历到 num ，生成的结果天然就是升序。
情况 2： taskA<taskB
- 斜率 <0，函数单调递减。
- 策略：让 i 从 num遍历到 0 ，生成的结果即为升序。
情况 3： taskA==taskB
- 斜率 =0 ，函数为常数。
- 策略：结果只有一个值 num×taskA 。

3. C语言实现难点与对策

字符串解析：C标准库没有split函数。
- 对策：使用strtok或手动遍历字符串查找逗号，配合atoll/atoi转换。
动态数组：C没有vector。
- 对策：根据num的大小，使用malloc动态分配足够大的数组（大小为num + 1）。
去重：
- 对策：在taskA == taskB时特殊处理，只分配 1 个元素的空间；其他情况所有值唯一，无需去重逻辑。
大数处理：
- 对策：必须使用long long类型存储时长和计算结果。

💻 三、C语言代码实现

本代码严格遵循 C99 标准，纯手工实现内存管理和字符串解析，无任何第三方依赖。

#include <stdio.h> #include <stdlib.h> #include <string.h> #include <ctype.h> // 辅助函数：去除字符串两端的空白字符 char* trim(char* str) { if (!str) return NULL; while (isspace((unsigned char)*str)) str++; if (*str == 0) return str; char* end = str + strlen(str) - 1; while (end > str && isspace((unsigned char)*end)) end--; end[1] = '\0'; return str; } int main() { char line[1024]; // 读取整行输入 if (fgets(line, sizeof(line), stdin) == NULL) { return 0; } // 解析输入 "taskA,taskB,num" // 使用 strtok 分割逗号 char* token = strtok(line, ","); if (!token) return 0; long long taskA = atoll(trim(token)); token = strtok(NULL, ","); if (!token) return 0; long long taskB = atoll(trim(token)); token = strtok(NULL, ","); if (!token) return 0; int num = atoi(trim(token)); // 确定结果数组的大小 int resultSize = 0; if (taskA == taskB) { resultSize = 1; } else { resultSize = num + 1; } // 动态分配内存 (使用 long long 防止溢出) long long* result = (long long*)malloc(resultSize * sizeof(long long)); if (!result) { fprintf(stderr, "Memory allocation failed\n"); return 1; } int idx = 0; if (taskA == taskB) { // 情况3：两者相等，结果只有一个 result[idx++] = num * taskA; } else if (taskA > taskB) { // 情况1：A > B，随 A 的数量增加，总时长增加 (升序) // i 代表 A 的数量，从 0 到 num for (int i = 0; i <= num; ++i) { result[idx++] = i * taskA + (long long)(num - i) * taskB; } } else { // 情况2：A < B，随 A 的数量增加，总时长减少 // 为了得到升序，我们需要让 A 的数量从多到少 (num -> 0) for (int i = num; i >= 0; --i) { result[idx++] = i * taskA + (long long)(num - i) * taskB; } } // 格式化输出 [3, 4, 5, 6] printf("["); for (int i = 0; i < resultSize; ++i) { printf("%lld", result[i]); if (i < resultSize - 1) { printf(", "); // 注意逗号后的空格 } } printf("]\n"); // 释放内存 free(result); return 0; }

💡 C语言代码亮点解析

手动内存管理：
- 使用malloc根据num精确分配所需内存，避免浪费。
- 使用完毕后立即free，养成良好的资源管理习惯，防止内存泄漏。
数据类型安全：
- 全程使用long long(对应%lld)。这是C语言处理大整数的标准方式，有效防止 105×109 导致的溢出。
- 显式强制转换(long long)(num - i)确保乘法运算在 64 位寄存器中进行。
字符串解析技巧：
- 使用strtok轻松按逗号分割字符串。
- 自定义trim函数去除输入中可能存在的空格，增强程序的鲁棒性（机考测试用例有时会有不规范的空格）。
- 使用atoll(ASCII to Long Long) 替代atoi，确保解析大数时不丢失精度。
零成本排序：
- 通过判断taskA和taskB的大小关系，控制for循环的遍历方向（正向或反向），直接生成有序数组。
- 优势：完全避免了调用qsort，将时间复杂度从 O(Nlog⁡N) 降低到 O(N) ，且代码逻辑清晰。

🔍 四、关键技术点对比

特性	C++ (`std::vector`)	Python (`list`)	C (原生)
数组管理	自动扩容，RAII	动态列表，自动管理	手动`malloc`/`free`
字符串分割	`stringstream`/`split`	`split()`	`strtok`/ 指针遍历
排序	`std::sort`	`sorted()`	数学单调性构造 (无排序)
大数支持	`long long`	自动大整数	`long long`
性能	高	中	极高 (无额外开销)

⚠️ 五、避坑指南（C语言特供版）

格式化占位符错误：
- ❌ 错误：printf("%d", long_long_var)。这会导致输出错误的值（通常只输出了低32位）。
- ✅ 正确：printf("%lld", long_long_var)。务必记住long long对应%lld。
内存泄漏：
- C语言不会自动回收malloc的内存。虽然程序结束操作系统会回收，但在函数内部或长期运行的服务中，忘记free是严重错误。
strtok的副作用：
- strtok会修改原字符串（将分隔符改为\0）。如果后续还需要原字符串，需要先strcpy备份。本题中不需要保留原串，直接使用即可。
缓冲区溢出：
- fgets(line, sizeof(line), stdin)限制了读取长度，防止输入过长导致栈溢出。定义line数组时要足够大（如 1024），足以容纳输入行。
输出格式细节：
- 再次强调：[3, 4, 5, 6]中逗号后有空格。C语言的printf需要手动控制这个空格，不能在join类操作中自动完成。