【最新华为OD机试E卷】报文响应时间(100分)

🍭 大家好这里是春秋招笔试突围 ，一枚热爱算法的程序员

💻 ACM金牌🏅️团队 ｜ 大厂实习经历 ｜ 多年算法竞赛经历

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

🧩 大部分包含 Python / C / Javascript / Java / Cpp 多语言代码

👏 感谢大家的订阅➕ 和 喜欢💗 和手里的小花花🌸

最新华为OD机试E卷全、新、准，题目覆盖率达 95% 以上，其中D卷题目全部支持在线评测，E卷题目敬请期待

最新华为OD机试专栏: https://www.nowcoder.com/creation/manager/columnDetail/MgbyJj

🎀关于华为OD

• ✨华为OD的概念 华为的大部分社会招聘采用了被称为OD（Outsourcing Dispatch）模式，这是一种与德科共同进行的招聘方式。在这种模式下，被招聘的员工通常被定级在13至17级，这些员工被视为华为的储备人才。华为每年会从这些OD项目中选拔表现出色的员工，并将他们转为正式员工。
• ⌚️华为 OD 应聘流程

  • 第一步：投递简历

    • 提供姓名、邮箱、手机号、身份证号，用于锁定，所以投递前需要考虑清楚，投到项目组之后，一般不会转给另一个项目的 HR 了，也就是被锁定。

  • 第二步：机试

    • 3 道算法题，400 分满分，一般 1 个月的准备时间，华为机试必须要 150 分以上，没有过半年之后才能参加下一次考试。

  • 第三步：技术面

    • 2 轮技术面试。

  • 第四步：HR 与主管面试

  • 第五步：录用，发 offer

🍓OJ题目截图

🪐 报文响应时间

问题描述

IGMP（Internet Group Management Protocol）协议中有一个字段称为最大响应时间（Max Response Time）。当主机（HOST）收到查询报文时，会解析出 MaxResponseTime 字段，并在 时间（秒）内选取一个随机时间来回应一个响应报文。如果在这个随机时间内收到一个新的查询报文，则会根据两者时间的大小，选取较小的一方来刷新回应时间。

0 1 2 3 4 5 6 7
+-+-+-+-+-+-+-+-+
|1| exp | mant |
+-+-+-+-+-+-+-+-+

最大响应时间的计算方式如下：

• 当 时，；
• 当 时，； 其中， 为最大响应时间的高 5~7 位， 为最大响应时间的低 4 位。

注意：接收到的 最大值为 255，所有字段均为无符号数。

现在假设 HOST 收到查询报文时，选取的随机时间必定为最大值。给定 HOST 收到的查询报文个数 ，每个查询报文的接收时间 和最大响应时间字段值 ，请计算出 HOST 发送响应报文的时间。

输入格式

第一行为查询报文个数 。 后续每行包含两个整数，分别为 HOST 收到报文时间 和最大响应时间 ，以空格分隔。

输出格式

输出一个整数，表示 HOST 发送响应报文的时间。

样例输入

3
0 20
1 10
8 20

样例输出

11

样例解释

收到 3 个报文：

1. 第 0 秒收到第 1 个报文，响应时间为 20 秒，则要到 秒响应；
2. 第 1 秒收到第 2 个报文，响应时间为 10 秒，则要到 秒响应，与上面的报文的响应时间比较获得响应时间最小为 11 秒；
3. 第 8 秒收到第 3 个报文，响应时间为 20 秒，则要到 秒响应，与上面的报文的响应时间比较获得响应时间最小为 11 秒；

最终得到最小响应报文时间为 11 秒。

样例输入

2
0 255
200 60

样例输出

260

样例解释

收到 2 个报文：

1. 第 0 秒收到第 1 个报文，响应时间为 255 秒，则要到 秒响应；(，)
2. 第 200 秒收到第 2 个报文，响应时间为 60 秒，则要到 秒响应，与上面的报文的响应时间比较获得响应时间最小为 260 秒；

最终得到最小响应报文时间为 260 秒。

数据范围

题解

这道题目的核心在于理解 IGMP 协议中最大响应时间的计算方式和主机选择响应时间的逻辑。

解题思路如下：

1. 对于每个查询报文，计算其最大响应时间。
2. 计算每个查询报文的最迟响应时间，即接收时间加上最大响应时间。
3. 在所有最迟响应时间中选择最小值，即为主机实际发送响应报文的时间。

关键点在于正确计算最大响应时间。当 Max Resp Code < 128 时，直接使用该值；当 Max Resp Code ≥ 128 时，需要按照给定公式计算。

时间复杂度分析：遍历所有查询报文一次，计算最大响应时间和更新最小最迟响应时间，总体时间复杂度为 O(C)，其中 C 是查询报文的数量。对于给定的数据范围（C ≤ 10^5），这个复杂度是可以接受的。

实现时，可以使用一个变量来维护当前的最小最迟响应时间，每处理一个查询报文就更新一次这个值。这样可以避免使用额外的数据结构，使得空间复杂度保持在 O(1)。

参考代码

• Python

def calculate_max_response_time(m):
    """
    计算最大响应时间
    :param m: Max Resp Code
    :return: 计算得到的最大响应时间
    """
    if m < 128:
        return m
    else:
        mant = m & 0x0F
        exp = (m & 0x70) >> 4
        return (mant | 0x10) << (exp + 3)

# 读取查询报文个数
C = int(input())

min_response_time = float('inf')  # 初始化最小响应时间为无穷大

# 处理每个查询报文
for _ in range(C):
    T, M = map(int, input().split())
    max_response_time = calculate_max_response_time(M)
    response_time = T + max_response_time
    min_response_time = min(min_response_tim