题解

题目描述

任务编排服务需要对两种不同执行时长的任务进行调度。在每次编排中，任务有两种类型：

1. 第1种任务执行时长为 taskA。
2. 第2种任务执行时长为 taskB。

每次可以编排的任务个数为 num，并且每次编排中，任务的顺序和任务的类型可以自由组合。我们需要输出所有可能的总执行时长，并且要求这些时长按从小到大的顺序排列。

解题思路

1. 问题分析：

   • 给定 taskA 和 taskB 的执行时长，以及 num 个任务的总数，任务的组合方式可以是：0个 taskA + num个 taskB，1个 taskA + num-1个 taskB，……，num个 taskA + 0个 taskB。
   • 对于每种组合，计算其总执行时长：i * taskA + (num - i) * taskB，其中 i 代表选择 taskA 的个数。

2. 步骤：

   • 从 i = 0 到 num，计算每一种组合的总执行时长。
   • 将所有结果存入一个集合中以去重，然后将其转换为列表并排序。

3. 时间复杂度：

   • 由于需要遍历从 0 到 num 的每一种组合，因此时间复杂度为 O(num)。去重操作的时间复杂度是 O(1)，排序的时间复杂度为 O(num log num)，因此总体时间复杂度为 O(num log num)。

Python代码

def task_schedule(input_str):
    # 解析输入
    taskA, taskB, num = map(int, input_str.split(','))
    
    # 使用set去重
    result = set()
    
    # 生成所有可能的总执行时长
    for i in range(num + 1):
        j = num - i  # j为taskB的数量
        total_time = i * taskA + j * taskB
        result.add(total_time)
    
    # 排序并返回结果
    return sorted(result)

# 输入
input_str = input().strip()
output = task_schedule(input_str)
print(output)

Java代码

import java.util.*;

public class Main {
    public static void main(String[] args) {
        // 读取输入
        Scanner sc = new Scanner(System.in);
        String input = sc.nextLine();
        
        // 分割输入并转换为整数
        String[] parts = input.split(",");
        int taskA = Integer.parseInt(parts[0]);
        int taskB = Integer.parseInt(parts[1]);
        int num = Integer.parseInt(parts[2]);
        
        // 使用Set去重
        Set<Integer> resultSet = new HashSet<>();
        
        // 生成所有可能的总执行时长
        for (int i = 0; i <= num; i++) {
            int j = num - i;
            resultSet.add(i * taskA + j * taskB);
        }
        
        // 将Set转换为List并排序
        List<Integer> result = new ArrayList<>(resultSet);
        Collections.sort(result);
        
        // 输出结果
        System.out.println(result);
    }
}

C++代码

#include <bits/stdc++.h>
using namespace std;

int main() {
    // 输入taskA, taskB, num 中间有逗号
    string input;
    getline(cin, input);
    stringstream ss(input);
    string token;
    vector<int> a;
    while (getline(ss, token, ',')) {
        a.push_back(stoi(token));
    }
    int taskA = a[0];
    int taskB = a[1];
    int num = a[2];
    
    // 使用set去重
    set<int> resultSet;
    
    // 生成所有可能的总执行时长
    for (int i = 0; i <= num; i++) {
        int j = num - i;
        resultSet.insert(i * taskA + j * taskB);
    }
    
    // 将set转换为vector并排序
    vector<int> result(resultSet.begin(), resultSet.end());
    
    // 输出结果
    cout << '[';
    for (int i = 0; i < result.size(); i++) {
        if (i != 0) cout << ", ";
        cout << result[i];
    }
    cout << ']' << endl;
    
    return 0;
}

题目内容

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

参与编排的任务有两种类型，其中一种执行时长为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和 1 次 taskB，得到结果 4 。以此类推，得到最终结果。