报文响应时间

题目描述

IGMP 协议中, 有一个字段称作最大响应时间 (Max Response Time), HOST收到查询报文, 解折出 MaxResponseTime 字段后, 需要在 (0，MaxResponseTime] 时间(秒)内选取随机时间回应一个响应报文. 如果在随机时间内收到一个新的查询报文, 则会根据两者时间的大小, 选取小的一方刷新回应时间.

最大响应时间有如下计算方式:

当 MaxRespCode < 128 时, MaxRespTime = MaxRespCode
当 MaxRespCode ≥ 128 时, MaxRespTime = (mant | 0x10) << (exp + 3)

注:

exp 最大响应时间的高5~7位
mant 为最大响应时间的低4位

其中接收到的 MaxRespCode 最大值为 255, 以上出现所有字段均为无符号数.

现在我们认为 HOST 收到查询报文时, 选取的随机时间必定为最大值, 现给出 HOST 收到查询报文个数 C, HOST 收到该报文的时间T, 以及查询报文的最大响应时间字段值 M, 请计算出 HOST 发送响应报文的时间.

输出:

说明:

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

示例2

输入:

2
0 255
200 60

输出:

说明:

收到2个报文
第0秒收到第1个报文, 响应时间为255秒, 则要到 (15 | 0x10) << (7 + 3)= 31744 秒响应, (mant = 15，exp = 7)
第200秒收到第2个报文, 响应时间为60秒, 则要到 200+60-260 秒响应, 与第上面的报文的响应时间比较获得响应时间最小为260秒
最终得到最小响应报文时间为260秒

题解

这个问题要搞明白如何进行位运算, 然后注意边界条件即可.

Python

import sys

def main():
    def get_resp_time(req_time):
        if req_time < 128:
            return req_time
        else:
            mant = req_time & 0b1111
            exp = (req_time >> 4 ) & 0b0110
            return (mant | 0x10) << (exp + 3)

    num_request = int(input().strip())

    # 读取所有的请求报文
    req_list = []
    for line in sys.stdin.readlines():
        parts = line.split()
        delay = int(parts[0])
        req_time = int(parts[1])
        req_list.append((delay, req_time))
    assert num_request == len(req_list)

    # 计算每个请求报文的响应时间, 并找到最小的值
    min_resp_time = 2 ** 32
    for delay, req_time in req_list:
        resp_time = get_resp_time(req_time)
        abs_resp_time = delay + resp_time
        min_resp_time = min(min_resp_time, abs_resp_time)
    print(min_resp_time)

if __name__ == "__main__":
    main()

C++

#include <cassert>
#include <climits>

#include <iostream>
#include <vector>

int get_resp_time(int req_time) {
  if (req_time < 128) {
    return req_time;
  } else {
    int mant = req_time & 0b1111;
    int exp = (req_time >> 4) & 0b0110;
    return (mant | 0x10) << (exp + 3);
  }
}

int main() {
  // 读取所有的请求报文

  int num_request = 0;
  std::cin >> num_request;

  std::vector<std::tuple<int, int>> req_list;
  int delay = 0;
  int req_time = 0;

  while (std::cin >> delay >> req_time) {
    req_list.emplace_back(delay, req_time);
  }
  assert(num_request == req_list.size());

  // 计算每个请求报文的响应时间, 并找到最小的值
  int min_resp_time = INT_MAX;
  for (const auto tuple: req_list) {
    int delay = std::get<0>(tuple);
    int req_time = std::get<1>(tuple);
    int resp_time = get_resp_time(req_time);
    int abs_resp_time = delay + resp_time;
    min_resp_time = std::min(min_resp_time, abs_resp_time);
  }

  std::cout << min_resp_time << std::endl;

  return 0;
}

Rust

use std::io::{stdin, BufRead};

fn get_resp_time(req_time: i32) -> i32 {
    if req_time < 128 {
        req_time
    } else {
        let mant: i32 = req_time & 0b1111;
        let exp: i32 = (req_time >> 4) & 0b0110;
        (mant | 0x10) << (exp + 3)
    }
}

fn main() {
    let mut line = String::new();
    let ret = stdin().lock().read_line(&mut line);
    assert!(ret.is_ok());
    let num_request: usize = line.trim().parse().unwrap();

    // 读取所有的请求报文
    let mut req_list = Vec::with_capacity(num_request);
    for line in stdin().lock().lines() {
        let line = line.unwrap();
        let mut parts = line.split_ascii_whitespace();
        let delay: i32 = parts.next().unwrap().parse().unwrap();
        let req_time: i32 = parts.next().unwrap().parse().unwrap();
        req_list.push((delay, req_time));
    }
    assert_eq!(num_request, req_list.len());

    // 计算每个请求报文的响应时间, 并找到最小的值
    let mut min_resp_time = i32::MAX;
    for (delay, req_time) in req_list {
        let resp_time = get_resp_time(req_time);
        let abs_resp_time = delay + resp_time;
        min_resp_time = min_resp_time.min(abs_resp_time);
    }

    println!("{min_resp_time}");
}

数据结构与算法 - Rust 语言实现

报文响应时间

题目描述

输入描述

输出描述

示例1

示例2

题解

Python

C++

Rust