【华为OD机试】真题A卷-快速开租建站（Python）

一、题目描述

【华为OD机试】真题A卷-快速开租建站（Python）

题目描述：

当前IT部门支撑了子公司颗粒化业务，该部门需要实现为子公司快速开租建站的能力，建站是指在一个全新的环境部署一套IT服务。

１：每个站点开站会由一系列部署任务项构成，每个任务项部署完成时间都是固定和相等的，设为1.

２：部署任务项之间可能存在依赖，假如任务2依赖任务1，那么等任务1部署完，任务2才能部署。

３：任务有多个依赖任务则需要等所有依赖任务都部署完该任务才能部署。

４：没有依赖的任务可以并行部署，优秀的员工们会做到完全并行无等待的部署。

给定一个站点部署任务项和它们之间的依赖关系，请给出一个站点的最短开站时间。

二、输入输出

输入描述：
第一行是任务数taskNum,
第二行是任务的依赖关系数relationsNum接下来 relationsNum 行，每行包含两个id，描述一个依赖关系，格式为: IDi　IDj，表示部署任务部署完成了，部署任务自容署，IDi 和 IDj值的范围为: [0,taskNum) 注: 输入保证部署任务之间的依赖不会存在环。
输出描述：
1个整数，表示一个站点的最短开站时间。
备注：
1 < taskNum ≤ 100
1 ≤ relationsNum ≤ 5000

三、参考示例

示例1：
输入：
5
5
0 4
1 2
1 3
2 3
2 4
输出：
3
说明：
先同时部署任务0和任务1，然后部署任务2，最后同时部署任务3和任务4.最短开站时间为3
示例2：
输入：
5
3
0 3
0 4
1 3
输出：
2
说明：
先同时部署任务0，任务1，任务2。然后再同时部署任务3和4.最短开站时间为2.

四、解题思路

1. 处理输入，读取任务数量和关系数量，以及任务之间的关系。
2. 初始化每个任务的入度和出度。
3. 遍历关系列表，更新每个任务的出度和入度。
4. 使用队列存储入度为0的任务，并设置初始耗时为1。
5. 遍历队列中的任务，更新相关任务的入度，如果入度为0，则更新耗时并加入队列。
6. 输出最终的耗时结果。

五、参考代码 

# -*- coding: utf-8 -*-
'''
@Time    :   2023/12/10 00:09:00
@Author  :   mgc 
@Version :   1.0
@Desc    :   None
'''

# import os
# import re
# import sys
# import copy
# import math
# import queue
# import functools
# from queue import Queue
# from collections import Counter, defaultdict

import sys

# 处理输入
num_tasks = int(input())
num_relations = int(input())
relations = []
for _ in range(num_relations):
    relations.append([int(x) for x in input().split(" ")])  # 添加缺失的右括号

# 初始化每个任务的入度和出度
in_degrees = [0 for _ in range(num_tasks)]
out_edges = [[] for _ in range(num_tasks)]

# 初始化入度和出度
for relation in relations:
    out_edges[relation[0]].append(relation[1])
    in_degrees[relation[1]] += 1

# 使用队列来存储入度为0的任务
queue = []
result_time = 1

for i in range(num_tasks):
    # 将所有入度为0的任务加入队列，默认耗时为1
    if in_degrees[i] == 0:
        queue.append([i, result_time])

while len(queue) > 0:
    current_task = queue.pop(0)
    task_id = current_task[0]
    time = current_task[1]

    for downstream_task in out_edges[task_id]:
        # 当前任务的入度减少到0时，放入队列中
        in_degrees[downstream_task] -= 1
        if in_degrees[downstream_task] == 0:
            result_time = time + 1
            queue.append([downstream_task, result_time])

print(result_time)

六、华为OD机试真题汇总目录

    【华为OD机试】真题汇总A+B+C+D券（Python实现）

    【华为OD机试】真题汇总A+B+C+D卷（JAVA实现）

    【华为OD机试】真题汇总A+B+C+D卷（C++实现）