E卷-报文响应时间(100分)

报文响应时间

问题描述

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_time, response_time)

# 输出最终的响应时间
print(int(min_response_time))

• C

#include <stdio.h>
#include <limits.h>

// 计算最大响应时间
unsigned int calculate_max_response_time(unsigned int m) {
    if (m < 128) {
        return m;
    } else {
        unsigned int mant = m & 0x0F;
        unsigned int exp = (m & 0x70) >> 4;
        return (mant | 0x10) << (exp + 3);
    }
}

int main() {