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() {
    int C;
    scanf("%d", &C);

    unsigned long long min_response_time = ULLONG_MAX;  // 初始化最小响应时间为最大值

    // 处理每个查询报文
    for (int i = 0; i < C; i++) {
        unsigned int T, M;
        scanf("%u %u", &T, &M);
        unsigned int max_response_time = calculate_max_response_time(M);
        unsigned long long response_time = (unsigned long long)T + max_response_time;
        if (response_time < min_response_time) {
            min_response_time = response_time;
        }
    }

    // 输出最终的响应时间
    printf("%llu\n", min_response_time);

    return 0;
}

• Javascript

const readline = require('readline');
const rl = readline.createInterface({
    input: process.stdin,
    output: process.stdout
});

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

let C;
let lineCount = 0;
let minResponseTime = Number.POSITIVE_INFINITY;

rl.on('line', (line) => {
    if (lineCount === 0) {
        C = parseInt(line);
    } else {
        const [T, M] = line.split(' ').map(Number);
        const maxResponseTime = calculateMaxResponseTime(M);
        const responseTime = T + maxResponseTime;
        minResponseTime = Math.min(minResponseTime, responseTime);

        if (lineCount === C) {
            console.log(Math.floor(minResponseTime));
            rl.close();
        }
    }
    lineCount++;
});

• Java

import java.util.Scanner;

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

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int C = scanner.nextInt();

        long minResponseTime = Long.MAX_VALUE;

        // 处理每个查询报文
        for (int i = 0; i < C; i++) {
            long T = scanner.nextLong();
            int M = scanner.nextInt();
            long maxResponseTime = calculateMaxResponseTime(M);
            long responseTime = T + maxResponseTime;
            minResponseTime = Math.min(minResponseTime, responseTime);
        }

        // 输出最终的响应时间
        System.out.println(minResponseTime);

        scanner.close();
    }
}

• Cpp

#include <iostream>
#include <climits>
#include <algorithm>

using namespace std;

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

int main() {
    int C;
    cin >> C;

    unsigned long long minResponseTime = ULLONG_MAX;  // 初始化最小响应时间为最大值

    // 处理每个查询报文
    for (int i = 0; i < C; i++) {
        unsigned int T, M;
        cin >> T >> M;
        unsigned long long maxResponseTime = calculateMaxResponseTime(M);
        unsigned long long responseTime = (unsigned long long)T + maxResponseTime;
        minResponseTime = min(minResponseTime, responseTime);
    }

    // 输出最终的响应时间
    cout << minResponseTime << endl;

    return 0;
}