最新华为OD机试真题-启动多任务排序(200分)

🍭 大家好这里是清隆学长 ，一枚热爱算法的程序员

✨ 本系列打算持续跟新华为OD-C/D卷的三语言AC题解

💻 ACM银牌🥈| 多次AK大厂笔试 ｜ 编程一对一辅导

👏 感谢大家的订阅➕ 和 喜欢💗

📎在线评测链接

=> 启动多任务排序(200分) <=

🌍 评测功能需要 =>订阅专栏<= 后联系清隆解锁～

🍓OJ题目截图

启动多任务排序

问题描述

卢小姐在开发一个应用程序，启动时需要执行多个初始化任务。这些任务之间可能存在依赖关系，例如任务 依赖任务 ，那么必须在任务 执行完成之后，才能开始执行任务 。现在给出多条任务依赖关系的规则，请输出任务的执行顺序。规则采用贪心策略，即如果一个任务没有依赖的任务，则立即开始执行；如果同时有多个任务可以执行，则按照任务名称的字母顺序排序。

例如，如果任务 依赖任务 ，任务 依赖任务 ，任务 依赖任务 和任务 ，同时任务 还依赖任务 ，那么执行任务的顺序应该是：任务 、任务 、任务 、任务 、任务 。这里任务 和任务 都是没有依赖的，可以立即执行。

输入格式

输入由若干个任务依赖规则组成，每个规则表示两个任务之间的依赖关系。规则使用符号 -> 表示依赖方向，例如 A->B 表示任务 依赖任务 。多个依赖规则之间用单个空格分隔。

输出格式

输出为排序后的启动任务列表，多个任务之间用单个空格分隔。

样例输入

A->B C->B

样例输出

B A C

数据范围

任务名称为大写字母 到 ，输入数据保证任务依赖关系合法且无循环依赖。

题解

本题可以使用拓扑排序来解决。首先，根据输入的任务依赖规则，构建任务之间的有向图。然后，统计每个任务的入度（即有多少个任务依赖当前任务）。

接下来，将所有入度为 的任务加入队列，表示这些任务可以立即执行。每次从队列中取出一个任务，将其加入结果列表，并将该任务指向的所有任务的入度减 。如果减 后某个任务的入度变为 ，则将其加入队列。

重复上述过程，直到队列为空。最后，按照结果列表中任务的顺序输出即可。

如果同时有多个任务可以执行，则按照任务名称的字母顺序排序后再加入结果列表。

时间复杂度为 ，其中 为任务数量， 为任务依赖关系数量。空间复杂度为 。

参考代码

• Python

from collections import deque

def main():
    rules = input().split()
    n = len(rules)
    in_degree = [0] * 26
    graph = [[] for _ in range(26)]
    vis = [False] * 26

    for rule in rules:
        a = ord(rule[0]) - ord('A')
        b = ord(rule[3]) - ord('A')
        in_degree[a] += 1
        graph[b].append(a)
        vis[a] = vis[b] = True

    q = deque()
    res = []
    tmp = []

    for i in range(26):
        if in_degree[i] == 0 and vis[i]:
            q.append(i)
            tmp.append(i)

    while q:
        tmp.sort()
        res.extend(tmp)
        tmp.clear()

        for _ in range(len(q)):
            task = q.popleft()
            for nxt in graph[task]:
                in_degree[nxt] -= 1
                if in_degree[nxt] == 0:
                    q.append(nxt)
                    tmp.append(nxt)

    print(' '.join(chr(x + ord('A')) for x in res))

if __name__ == '__main__':
    main()

• Java

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        String[] rul