报文响应时间

问题描述

IGMP 里有一个 Max Response Time 字段。HOST 收到查询报文后，要在 ((0, \textit{MaxRespTime}]) 秒内回一个响应。题目约定：HOST 总是取这个区间的最大值 作为回应时刻。

如果在等待期间又收到新的查询报文，就用两边截止时间里更早的那个刷新。

MaxRespCode（记作 (M)，0～255 的无符号数）换算成秒数的规则来自 RFC 3376：

• (M < 128)：(\textit{MaxRespTime} = M)
• (M \ge 128)：把 (M) 拆成 1 位标志 + 3 位 exp + 4 位 mant

  7 6 5 4 3 2 1 0
 +-+-+-+-+-+-+-+-+
 |1|  exp  |mant |
 +-+-+-+-+-+-+-+-+
 MaxRespTime = (mant | 0x10) << (exp + 3)

也就是 exp = (M >> 4) & 7，mant = M & 15。(M = 255) 时：mant = 15，exp = 7，时间为 ((15 | 16) \ll 10 = 31744) 秒。

给出 (C) 条查询：收到时刻 (T) 和字段 (M)，求 HOST 真正发出响应的时刻。

输入

• 第一行：整数 (C)，查询报文个数
• 接下来 (C) 行：每行两个整数 (T) (M)，收到时刻和最大响应字段

输出

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

示例

输入：

3
0 20
1 10
8 20

输出：

11

• 第 0 秒，(M=20 < 128)，截止 20
• 第 1 秒，截止 (1+10=11)，比 20 更早，刷新为 11
• 第 8 秒，截止 (8+20=28)，已经晚于 11，不改

输入：

2
0 255
200 60

输出：

260

第一条按公式得到 31744；第二条 (200+60=260)，取更早的 260。

思路

按到达顺序扫一遍：

1. 把 (M) 解码成秒数。小于 128 原样用；否则按上面的位移公式。
2. 当前报文的截止时间是 (T + \textit{MaxRespTime})。
3. 维护全局最早截止时间 ans。新报文只有在 T < ans 时才还赶得上（还没发出去），这时 ans = min(ans, T + t)。

复杂度 (O(C))。

注意：exp 是 bit 4～6，不是 bit 5～7。写成 (M >> 5) & 7 会把 255 解成错的秒数。

参考代码

Python3

def max_resp_time(m):
    if m < 128:
        return m
    exp = (m >> 4) & 7
    mant = m & 15
    return (mant | 0x10) << (exp + 3)

c = int(input())
ans = 10**18
for _ in range(c):
    t, m = map(int, input().split())
    if t >= ans:
        continue
    ans = min(ans, t + max_resp_time(m))
print(ans)

Java

import java.util.Scanner;

public class Main {
    static int maxRespTime(int m) {
        if (m < 128) return m;
        int exp = (m >> 4) & 7;
        int mant = m & 15;
        return (mant | 0x10) << (exp + 3);
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int c = sc.nextInt();
        long ans = Long.MAX_VALUE;
        for (int i = 0; i < c; i++) {
            int t = sc.nextInt();
            int m = sc.nextInt();
            if (t >= ans) continue;
            ans = Math.min(ans, t + (long) maxRespTime(m));
        }
        System.out.println(ans);
    }
}

C++

#include <iostream>
#include <algorithm>
#include <cstdint>
using namespace std;

int maxRespTime(int m) {
    if (m < 128) return m;
    int exp = (m >> 4) & 7;
    int mant = m & 15;
    return (mant | 0x10) << (exp + 3);
}

int main() {
    int c;
    cin >> c;
    long long ans = 1e18;
    for (int i = 0; i < c; i++) {
        int t, m;
        cin >> t >> m;
        if (t >= ans) continue;
        ans = min(ans, t + (long long)maxRespTime(m));
    }
    cout << ans << '\n';
    return 0;
}

C语言

#include <stdio.h>
#include <stdint.h>

static int max_resp_time(int m) {
    if (m < 128) return m;
    int exp = (m >> 4) & 7;
    int mant = m & 15;
    return (mant | 0x10) << (exp + 3);
}

int main(void) {
    int c;
    scanf("%d", &c);
    long long ans = 1000000000000000000LL;
    for (int i = 0; i < c; i++) {
        int t, m;
        scanf("%d %d", &t, &m);
        if ((long long)t >= ans) continue;
        long long deadline = t + (long long)max_resp_time(m);
        if (deadline < ans) ans = deadline;
    }
    printf("%lld\n", ans);
    return 0;
}

JSNode

const readline = require('readline');
const rl = readline.createInterface({ input: process.stdin, output: process.stdout });
const lines = [];
rl.on('line', (line) => lines.push(line.trim()));
rl.on('close', () => {
    const maxRespTime = (m) => {
        if (m < 128) return m;
        const exp = (m >> 4) & 7;
        const mant = m & 15;
        return (mant | 0x10) << (exp + 3);
    };
    const c = parseInt(lines[0], 10);
    let ans = Number.POSITIVE_INFINITY;
    for (let i = 0; i < c; i++) {
        const [t, m] = lines[i + 1].split(/\s+/).map(Number);
        if (t >= ans) continue;
        ans = Math.min(ans, t + maxRespTime(m));
    }
    console.log(ans);
});

Go

package main

import "fmt"

func maxRespTime(m int) int {
    if m < 128 {
        return m
    }
    exp := (m >> 4) & 7
    mant := m & 15
    return (mant | 0x10) << (exp + 3)
}

func main() {
    var c int
    fmt.Scan(&c)
    ans := int64(1 << 62)
    for i := 0; i < c; i++ {
        var t, m int
        fmt.Scan(&t, &m)
        if int64(t) >= ans {
            continue
        }
        d := int64(t) + int64(maxRespTime(m))
        if d < ans {
            ans = d
        }
    }
    fmt.Println(ans)
}