一、题目描述题目描述任务编排服务负责对任务进行组合调度。参与编排的任务有两种类型其中一种执行时长为taskA另一种执行时长为taskB。任务一旦开始执行不能被打断且任务可连续执行。服务每次可以编排num个任务。请编写一个方法生成每次编排后的任务所有可能的总执行时长。输入描述第1行输入分别为第1种任务执行时长taskA第2种任务执行时长taskB这次要编排的任务个数num以逗号分隔。输出描述数组形式返回所有总执行时时长需要按从小到大排列。补充说明:每种任务的数量都大于本次可以编排的任务数量。0taskA0taskB0num100000示例1输入1,2,3输出[3, 4, 5, 6]说明可以执行3次taskA得到结果3执行2次taskA和次taskB得到结果4。以此类推得到最终结果。二、解题思路深度解析1. 数学建模设选择任务A的数量为 i 则任务B的数量为 num−i 其中 0≤i≤num 。总时长 T(i) 的公式为T(i)i×taskA(num−i)×taskB整理得T(i)i×(taskA−taskB)num×taskB这是一个关于 ii 的一次函数线性函数。2. 单调性分析核心优化点根据斜率 ktaskA−taskB 的正负函数的单调性不同情况 1 taskAtaskB斜率 k0 函数单调递增。当 i 从 0 增加到 num 时 T(i) 从小到大排列。策略直接按 i0,1,...,num 顺序计算并存入数组天然有序。情况 2 taskAtaskB斜率 k0k0 函数单调递减。当 i 从 0 增加到 num 时 T(i) 从大到小排列。策略按 inum,num−1,...,0 逆序计算或者计算后反转数组即可得到升序结果。情况 3 taskAtaskBtaskAtaskB斜率 k0 函数为常数。无论 i 取何值 T(i) 均相等。策略结果集中只有一个值 num×taskA 。3. 算法优势时间复杂度 O(N) 。我们只需要遍历一次无需调用std::sort O(Nlog⁡N) 。在 N100,000 时效率提升显著。空间复杂度 O(N) 用于存储结果向量。去重处理利用上述逻辑当 AB 时单独处理自然避免了重复数据当 A≠B 时线性函数保证所有值唯一无需额外去重。三、C 代码实现本代码严格遵循 C11 标准使用long long防止溢出并利用单调性直接生成有序数组。#include iostream #include vector #include string #include sstream #include algorithm using namespace std; // 辅助函数分割字符串 vectorstring split(const string s, char delimiter) { vectorstring tokens; string token; istringstream tokenStream(s); while (getline(tokenStream, token, delimiter)) { tokens.push_back(token); } return tokens; } void solve() { string line; if (!getline(cin, line)) return; // 去除可能的空白字符虽然题目说是逗号分隔但健壮性很重要 // 简单处理split 后 trim vectorstring parts split(line, ,); if (parts.size() ! 3) return; // 转换为整数注意去除空格 long long taskA stoll(parts[0]); long long taskB stoll(parts[1]); int num stoi(parts[2]); vectorlong long result; // 预分配内存避免多次扩容 if (taskA taskB) { // 情况3两者相等结果只有一个 result.push_back(num * taskA); } else if (taskA taskB) { // 情况1A B随 A 的数量增加总时长增加 // i 代表 A 的数量从 0 到 num result.reserve(num 1); for (int i 0; i num; i) { long long total i * taskA (long long)(num - i) * taskB; result.push_back(total); } } else { // 情况2A B随 A 的数量增加总时长减少 // 为了得到升序我们需要让 A 的数量从多到少 (num - 0) // 或者 B 的数量从少到多 result.reserve(num 1); for (int i num; i 0; --i) { long long total i * taskA (long long)(num - i) * taskB; result.push_back(total); } } // 格式化输出 [3, 4, 5, 6] cout [; for (size_t i 0; i result.size(); i) { cout result[i]; if (i result.size() - 1) { cout , ; // 注意逗号后的空格 } } cout ] endl; } int main() { // 优化 IO 速度 ios_base::sync_with_stdio(false); cin.tie(NULL); solve(); return 0; } C 代码亮点解析数据类型安全使用long long存储taskA,taskB和计算结果。原因若taskA 10^9,num 10^5结果为 1014 远超int(2×109 ) 的范围。转换细节(long long)(num - i)确保乘法运算在 64 位下进行。单调性优化代码通过if-else判断taskA和taskB的大小关系决定循环的方向0-num或num-0。效果生成的result向量天然是升序的完全省去了std::sort的开销将时间复杂度锁定在 O(N) 。内存预分配result.reserve(num 1)预先分配足够的内存空间避免push_back过程中因容量不足导致的多次内存重新分配和数据拷贝提升运行效率。输入解析健壮性使用stringstream和getline进行逗号分割比手动查找字符位置更清晰。stoll和stoi自动处理字符串转数字并能忽略前后的空白符取决于具体实现这里配合 split 使用非常稳妥。IO 加速ios_base::sync_with_stdio(false); cin.tie(NULL);关闭 C 流与 C 标准流的同步解除cin与cout的绑定大幅提升大量数据输入输出时的性能。四、对比通用排序法 vs 单调性构造法表格特性通用排序法 (std::sort)单调性构造法 (本文方案)逻辑复杂度低无脑计算后排序中需判断大小关系决定遍历方向时间复杂度O(Nlog⁡N)O(N)空间复杂度O(N)O(N)去重处理需额外std::unique逻辑分支自然处理适用场景N 较小或对性能不敏感N 较大 (105 ) 或追求极致性能注在机考环境中 N100,000N100,000 时 O(Nlog⁡N)O(NlogN) 约为 1.7×1061.7×106 次操作通常也能 AC。但使用 O(N)O(N) 方案能体现候选人对算法特性的深刻理解是面试中的加分项。五、避坑指南⚠️整数溢出Overflow这是本题最大的坑。务必使用long long。如果使用int在大数据测试用例会得到错误答案WA。输出格式题目示例[3, 4, 5, 6]中逗号后面有一个空格。很多考生输出[3,4,5,6]无空格导致格式校验失败。请严格按照,拼接。相等情况当taskA taskB时如果不做特殊处理循环会生成 num1num1 个相同的值。题目问的是“所有可能的总时长”语义上指值的集合应输出[X]而非[X, X, ..., X]。代码中已专门处理此分支。输入分割不要直接用cin a b c因为输入是用逗号分隔的cin默认遇空格或换行停止无法自动跳过逗号。必须读取整行后手动分割。六、总结这道题考察了候选人的数学抽象能力和C 基础功底。数学层面识别出线性关系的单调性从而优化算法复杂度。工程层面注意数据范围long long、输入解析字符串分割和输出格式细节。C 特性合理利用vector预分配和 IO 加速展现写出高性能代码的能力。掌握这种“分析数学性质 - 定制遍历策略”的思维模式比单纯背诵排序算法更有价值。希望这篇 C 深度解析能助你在华为 OD 机考中脱颖而出觉得有用欢迎点赞、收藏、关注获取更多华为OD机试真题全语言解析