响应报文时间

题目描述

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

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

$MaxRespTime=\{\begin{array}{ll}MaxRespCode& MaxRespCode<128\\ (mant|0x10)<<(exp+3)& MaxRespCode\ge 128\end{array}$

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

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

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

输入描述
第一行为查询报文个数 $C$，后续每行分别为 HOST 收到报文时间 $T$，及最大响应时间$M$，以空格分割

输出描述
HOST 发送响应报文的时间。

补充说明
用例确定只会发送一个响应报文， 不存在计时结束后依然收到查询报文的情况。

示例1

输入

3
0 20
1 10
8 20

输出

11

说明

收到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

输出

260

说明

收到2个报文，
第0秒收到第1个报文，响应时间为255秒，则要到(15 | 0x10) << (7 + 3)= 31744秒响应; (mant = 15，exp =7)

第200秒收到第2个报文，响应时间为60秒，则要到200+60-260秒响应，与第上面的报文的响应时间比较获得响应时间最小为260秒:

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

题解

$MaxRespTime=\{\begin{array}{ll}MaxRespCode& MaxRespCode<128\\ (mant|0x10)<<(exp+3)& MaxRespCode\ge 128\end{array}$

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

源码

public class MaxRespTime {
	static Input input ;
	static {
		input = new Input("2\n" +
				"0 255\n" +
				"200 60");
		input = new Input("3\n" +
				"0 20\n" +
				"1 10\n" +
				"8 20");
	}

	public static void main(String[] args) {

		int n = Integer.parseInt(input.nextLine());
		int result = Integer.MAX_VALUE;
		for (int i = 0; i < n; i++) {
			String[] ss = input.nextLine().split(" ");
			int startTime = Integer.parseInt(ss[0]);
			int respTime = Integer.parseInt(ss[1]);
			if (respTime < 128) {
				result = Math.min(result, startTime + respTime);
			} else {
				int mant = respTime & 15; // 取得后四位
				int exp = respTime >> 4 & 7; // 取得 5~7位
				int resp = (mant | 0x10) << (exp + 3);
				result = Math.min(result, startTime + resp);
			}
		}
		System.out.println(result);
	}
}