题面描述

运维工程师采集到某产品线网运行一天产生的日志，共有 $n$ 条，需根据日志时间先后顺序对其进行排序。日志时间格式为 $H:M:S.N$，其中 $H$ 表示小时（$0$~$23$），$M$ 表示分钟（$0$~$59$），$S$ 表示秒（$0$~$59$），$N$ 表示毫秒（$0$~$999$）。时间可能未补全，例如 01:01:01.001 可能表示为 1:1:1.1。输入的第一行为日志条数 $n$（$1 \leq n \leq 100000$），接下来 $n$ 行输入时间。输出时需按时间升序排序，且若时间相同，则保持输入顺序。

思路

1. 解析时间字符串：将每个时间字符串按照 H:M:S.N 的格式分割，并将各部分转换为整数。

2. 计算总毫秒数：为了方便比较，将每个时间转换为总毫秒数，计算公式为：

   total_ms = H * 3600000 + M * 60000 + S * 1000 + N

3. 保持稳定排序：由于需要在时间相同的情况下保持输入顺序，选择稳定的排序算法。C++ 中的 stable_sort 函数能够满足这一要求。

4. 存储原始时间字符串：为了在排序后输出原始格式的时间，需要在存储总毫秒数的同时保存原始的时间字符串。

5. 排序并输出：根据总毫秒数进行排序，排序完成后按顺序输出原始时间字符串。

cpp

#include <bits/stdc++.h>
using namespace std;

// 定义一个结构体来存储时间的总毫秒数和原始时间字符串
struct Log {
    long long total_ms; // 总毫秒数
    string original;    // 原始时间字符串
};

// 函数用于解析时间字符串并计算总毫秒数
long long parseTime(const string& timeStr) {
    int H = 0, M = 0, S = 0, N = 0;
    int pos1 = timeStr.find(':');
    H = stoi(timeStr.substr(0, pos1));
    
    int pos2 = timeStr.find(':', pos1 + 1);
    M = stoi(timeStr.substr(pos1 + 1, pos2 - pos1 - 1));
    
    int pos3 = timeStr.find('.', pos2 + 1);
    S = stoi(timeStr.substr(pos2 + 1, pos3 - pos2 - 1));
    
    // 如果没有小数点，毫秒为0
    if (pos3 != string::npos) {
        string msStr = timeStr.substr(pos3 + 1);
        N = stoi(msStr);
    }
    
    return static_cast<long long>(H) * 3600000 + static_cast<long long>(M) * 60000 
           + static_cast<long long>(S) * 1000 + N;
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    
    int n;
    cin >> n;
    vector<Log> logs(n);
    
    for(int i = 0; i < n; ++i){
        cin >> logs[i].original;
        logs[i].total_ms = parseTime(logs[i].original);
    }
    
    // 稳定排序，按总毫秒数升序
    stable_sort(logs.begin(), logs.end(), [&](const Log &a, const Log &b) -> bool{
        return a.total_ms < b.total_ms;
    });
    
    // 输出排序后的原始时间字符串
    for(auto &log : logs){
        cout << log.original << "\n";
    }
    
    return 0;
}

python

import sys

def parse_time(time_str):
    parts = time_str.strip().split(':')
    H = int(parts[0])
    M = int(parts[1])
    S, N = 0, 0
    if '.' in parts[2]:
        S_part, N_part = parts[2].split('.')
        S = int(S_part)
        N = int(N_part)
    else:
        S = int(parts[2])
    total_ms = H * 3600000 + M * 60000 + S * 1000 + N
    return total_ms

def main():
    input = sys.stdin.read().splitlines()
    n = int(input[0])
    logs = []
    for i in range(1, n+1):
        time_str = input[i]
        total_ms = parse_time(time_str)
        logs.append( (total_ms, i, time_str) )
    # 使用稳定的排序，首先按总毫秒数
    logs.sort(key=lambda x: x[0])
    for log in logs:
        print(log[2])

if __name__ == "__main__":
    main()

java

import java.io.*;
import java.util.*;

public class Main {
    // 定义一个类来存储时间的总毫秒数和原始时间字符串以及输入顺序
    static class Log {
        long totalMs;
        String original;
        int index; // 输入顺序

        Log(long totalMs, String original, int index){
            this.totalMs = totalMs;
            this.original = original;
            this.index = index;
        }
    }

    // 函数用于解析时间字符串并计算总毫秒数
    static long parseTime(String timeStr){
        String[] parts = timeStr.split(":");
        int H = Integer.parseInt(parts[0]);
        int M = Integer.parseInt(parts[1]);
        int S = 0, N = 0;
        if(parts[2].contains(".")){
            String[] secParts = parts[2].split("\\.");
            S = Integer.parseInt(secParts[0]);
            N = Integer.parseInt(secParts[1]);
        }
        else{
            S = Integer.parseInt(parts[2]);
        }
        return (long)H * 3600000 + (long)M * 60000 + (long)S * 1000 + N;
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        List<Log> logs = new ArrayList<>();
        for(int i = 0; i < n; i++){
            String timeStr = br.readLine();
            long totalMs = parseTime(timeStr);
            logs.add(new Log(totalMs, timeStr, i));
        }
        // 使用稳定的排序，首先按总毫秒数，保持输入顺序
        Collections.sort(logs, new Comparator<Log>(){
            public int compare(Log a, Log b){
                if(a.totalMs != b.totalMs){
                    return Long.compare(a.totalMs, b.totalMs);
                }
                else{
                    return Integer.compare(a.index, b.index);
                }
            }
        });
        // 输出排序后的原始时间字符串
        StringBuilder sb = new StringBuilder();
        for(Log log : logs){
            sb.append(log.original).append("\n");
        }
        System.out.print(sb.toString());
    }
}

题目描述

运维工程师采集到某产品线网运行一天产生的日志 $n$ 条，现需根据日志时间先后顺序对日志进行排序，日志时间格式为 $H:M:S.N$ 。

$H$ 表示小时($0$~$23$)

$M$ 表示分钟($0$~$59$)

$S$ 表示秒($0$~$59$)

$N$ 表示毫秒($0$~$999$)

时间可能并没有补全，也就是说，$01:01:01.001$ 也可能表示为 $1:1:1.1$ 。

输入描述

第一行输入一个整数 $n$ 表示日志条数，$1<=n<=100000$ ，接下来 $n$ 行输入 $n$ 个时间。

输出描述

按时间升序排序之后的时间，如果有两个时间表示的时间相同，则保持输入顺序。

样例1

输入

2
01:41:8.9
1:1:09.211

输出

1:1:09.211
01:41:8.9

样例2

输入

3
23:41:08.023
1:1:09.211
08:01:22.0

输出

1:1:09.211
08:01:22.0
23:41:08.023

样例3

输入

2
22:41:08.023
22:41:08.23

输出

22:41:08.023
22:41:08.23

说明

两个时间表示的时间相同，保持输入顺序