刷题笔记合集🔗

任务总执行时长

问题描述

任务编排服务负责对任务进行组合调度。

参与编排的任务有两种类型，其中一种执行时长为 ，另一种执行时长为 。

任务一旦开始执行不能被打断，且任务可连续执行。

服务每次可以编排 个任务。

请编写一个方法，生成每次编排后的任务所有可能的总执行时长。

输入格式

第 行输入分别为第 种任务执行时长 ，第 种任务执行时长 ，这次要编排的任务个数 ，以逗号分隔。

注：每种任务的数量都大于本次可以编排的任务数量

输出格式

数组形式返回所有总执行时长，需要按从小到大排列。

样例输入

1,2,3

样例输出

[3, 4, 5, 6]

数据范围

题解

这道题目看起来可能有些复杂，但实质上是一个简单的组合问题，关键在于理解问题的本质。

题目要求我们找出所有可能的任务总执行时长。我们有两种任务类型，分别需要taskA和taskB的时间来执行，总共要安排num个任务。

每种可能的总执行时长可以用下面的公式表示： total_time = i * taskA + (num - i) * taskB，其中i表示类型A任务的数量，范围从0到num。

例如在样例中，taskA=1，taskB=2，num=3，我们可以组合出以下几种情况：

• 3个类型A任务，0个类型B任务：3 * 1 + 0 * 2 = 3
• 2个类型A任务，1个类型B任务：2 * 1 + 1 * 2 = 4
• 1个类型A任务，2个类型B任务：1 * 1 + 2 * 2 = 5
• 0个类型A任务，3个类型B任务：0 * 1 + 3 * 2 = 6

所以所有可能的总执行时长为[3, 4, 5, 6]。

还有一个特殊情况需要考虑：如果taskA等于taskB，那么无论怎么组合，总执行时长都只有一种可能，即num * taskA。

这个解法的时间复杂度是O(num)，因为我们需要考虑从0到num的每个i值。空间复杂度是O(num+1)，用于存储所有可能的总执行时长。鉴于题目给出的num可能高达100000，这个算法在处理大规模输入时仍然高效。

参考代码

• Python

import sys
input = lambda:sys.stdin.readline().strip()

# 读取输入
taskA, taskB, num = map(int, input().split(','))

# 计算所有可能的执行时长
def get_possible_durations(taskA, taskB, num):
    # 特殊情况：如果任务A和任务B的执行时间相同
    if taskA == taskB:
        # 只有一种可能的执行时长
        return [taskA * num] if num > 0 else []
    
    # 一般情况：计算所有可能的执行时长
    durations = set()
    for i in range(num + 1):
        # i个任务A和(num-i)个任务B的组合
        duration = i * taskA + (num - i) * taskB
        durations.add(duration)
    
    # 按照从小到大排序
    return sorted(durations)

# 获取结果
result = get_p