题解 | #星尘轨迹分析#

题目链接

星尘轨迹分析

题目描述

分析一批天体观测数据，数据格式为 id t，其中 $id$ 是天体标识符， $t$ 是观测时间戳。数据已按时间戳 $t$ 升序排列。

定义“观测间隔”为某次观测与前一次观测的时间差。对于任务的第一次观测，其观测间隔为该次观测的时间戳与 $0$ 的差。

任务是找出产生最短观测间隔和最长观测间隔的天体 $id$ 。如果多个天体的观测间隔相同，则选择数值最小的那个天体 $id$ 。

输入:

多行输入，每行包含一个天体标识符 $id$ 和一个时间戳 $t$ ，由空格分隔。

输出:

一行输出两个整数，分别是具有最短观测间隔的天体 $id$ 和具有最长观测间隔的天体 $id$ 。

解题思路

这是一个模拟和最值求解问题。由于输入数据已经按照时间戳 $t$ 进行了排序，我们可以一次遍历就解决问题。

我们需要维护几个变量：

$prev_t$ ：上一次观测的时间戳，初始为 $0$ 。
$min_interval$ ：记录当前找到的最短观测间隔，初始为一个极大值。
$max_interval$ ：记录当前找到的最长观测间隔，初始为一个极小值（例如 $-1$ ）。
$min_id$ ：与最短观测间隔对应的天体 $id$ 。
$max_id$ ：与最长观测间隔对应的天体 $id$ 。

遍历每一条观测记录 ( $id$ , $t$ )：

计算当前观测间隔： $\Delta t = t - prev_t$ 。
更新最短间隔信息：
- 如果 $\Delta t < min_interval$ ，说明我们找到了一个新的更短的间隔。更新 $min_interval = \Delta t$ 和 $min_id = id$ 。
- 如果 $\Delta t = min_interval$ ，发生了并列情况。根据题意，选择数值更小的 $id$ ，即 $min_id = \min(min_id, id)$ 。
更新最长间隔信息：
- 如果 $\Delta t > max_interval$ ，说明我们找到了一个新的更长的间隔。更新 $max_interval = \Delta t$ 和 $max_id = id$ 。
- 如果 $\Delta t = max_interval$ ，发生了并列情况。根据题意，选择数值更小的 $id$ ，即 $max_id = \min(max_id, id)$ 。
更新上一次观测的时间戳： $prev_t = t$ ，为下一次计算做准备。

遍历结束后， $min_id$ 和 $max_id$ 就是我们要求的结果。

代码

c++
java
python

#include <iostream>
#include <algorithm>
#include <limits>

using namespace std;

int main() {
    int id, t;
    int prev_t = 0;
    
    // 初始化最短和最长间隔信息
    int min_interval = numeric_limits<int>::max();
    int max_interval = -1;
    int min_id = 0;
    int max_id = 0;

    // 逐行读取输入
    while (cin >> id >> t) {
        // 计算当前观测间隔
        int interval = t - prev_t;
        
        // 更新最短间隔信息
        if (interval < min_interval) {
            min_interval = interval;
            min_id = id;
        } else if (interval == min_interval) {
            min_id = min(min_id, id);
        }
        
        // 更新最长间隔信息
        if (interval > max_interval) {
            max_interval = interval;
            max_id = id;
        } else if (interval == max_interval) {
            max_id = min(max_id, id);
        }
        
        // 更新上一个时间戳
        prev_t = t;
    }
    
    // 输出结果
    cout << min_id << " " << max_id << endl;
    
    return 0;
}

import java.util.Scanner;
import java.lang.Math;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        
        int prev_t = 0;
        
        // 初始化最短和最长间隔信息
        int min_interval = Integer.MAX_VALUE;
        int max_interval = -1;
        int min_id = 0;
        int max_id = 0;

        // 逐行读取输入
        while (sc.hasNextInt()) {
            int id = sc.nextInt();
            int t = sc.nextInt();
            
            // 计算当前观测间隔
            int interval = t - prev_t;
            
            // 更新最短间隔信息
            if (interval < min_interval) {
                min_interval = interval;
                min_id = id;
            } else if (interval == min_interval) {
                min_id = Math.min(min_id, id);
            }
            
            // 更新最长间隔信息
            if (interval > max_interval) {
                max_interval = interval;
                max_id = id;
            } else if (interval == max_interval) {
                max_id = Math.min(max_id, id);
            }
            
            // 更新上一个时间戳
            prev_t = t;
        }
        
        // 输出结果
        System.out.println(min_id + " " + max_id);
    }
}

import sys

# 初始化上一个时间戳
prev_t = 0

# 初始化最短和最长间隔信息
min_interval = float('inf')
max_interval = -1
min_id = 0
max_id = 0

# 逐行读取输入
for line in sys.stdin:
    parts = line.split()
    if not parts:
        continue
    id = int(parts[0])
    t = int(parts[1])
    
    # 计算当前观测间隔
    interval = t - prev_t
    
    # 更新最短间隔信息
    if interval < min_interval:
        min_interval = interval
        min_id = id
    elif interval == min_interval:
        min_id = min(min_id, id)
        
    # 更新最长间隔信息
    if interval > max_interval:
        max_interval = interval
        max_id = id
    elif interval == max_interval:
        max_id = min(max_id, id)
    
    # 更新上一个时间戳
    prev_t = t

# 输出结果
print(min_id, max_id)

算法及复杂度

算法：单次遍历 + 最值求解
时间复杂度： $\mathcal{O}(N)$ ，其中 $N$ 是观测记录的总数。我们只需要对输入数据进行一次线性扫描。
空间复杂度： $\mathcal{O}(1)$ ，我们只使用了有限的几个变量来存储状态，与输入规模无关。