华为OD机考双机位B/C卷 - 压缩日志查询 (C++ Python JAVA JS C)-深圳市維司達科技有限公司

题目描述

某设备需要记录每分钟检测到的指标值。为了节约存储空间，将连续相同指标值的记录合并。

压缩之前： 202411231000,11 202411231001,11 202411231002,12 202411231003,12 202411231004,10 202411231005,17 202411231006,17 202411231007,17

压缩之后： 202411231000,202411231001,11 202411231002,202411231003,12 202411231004,202411231004,10 202411231005,202411231007,17

查询时，根据输入的时间范围进行查询，需要返回回时间范围内记录的每分钟的指标值，如果某个时间点没有记录值，则此条记录忽略不返回。

输入描述

第一行为查询的时间范围，格式是：startTime,endTime。查询的时间范围为闭区间，即大于等于startTime且小于等于endTime， startTime <= endTime，且他们跨度的分钟数小于100；

第二行为压缩日志记录的行数，100 >= N > 0；

第三行及以后为压缩日志内容。每一行的格式为：startTime,endTime,kpi，其中 startTime<=endTime，10^5>kpi>=0；记录已按升序进行排序。

不保证两行记录之间是紧密连接，startTime和endTime的时间跨度可能很大。如：上一行的数据显示范围是202411231540, 202411231542，下一行的数据显示可以是 202411231544, 202411231547，中间202411231543的数据可能由于其他原因缺失。

输出描述

输出描述查询到的日志清单，如： 202411231010,11 202411231011,10 202411231012,10 202411231013,16

输出结果按数据时间升序排序。

补充说明输入的数据可能超出当前已存储的数据范围，此时只输出查询到的数据。如果从头到尾都没有查询到记录，则输出-1。

用例1

输入

202411231010,202411231013

4

202411231000,202411231010,11

202411231011,202411231012,10

202411231013,202411231020,16

202411231021,202411231028,17

输出

202411231010,11

202411231011,10

202411231012,10

202411231013,16

说明

202411231010时间的指标值在202411231000,202411231010范围内，值是11 202411231011,202411231012时间的指标值在202411231011,202411231012范围内，值是10 202411231013时间的指标值在202411231013,202411231020范围内，值是16

问题分析

题目要求处理压缩后的时间序列数据，并根据查询范围恢复每分钟的原始数据。压缩数据格式为startTime,endTime,value，表示从startTime到endTime（闭区间）每分钟的指标值均为value。查询时需要将压缩数据解压为每分钟的记录，并筛选出落在查询时间范围内的记录。

解决思路

解析查询范围：获取查询的起始时间和结束时间。
处理压缩数据：遍历每条压缩记录，检查其时间范围是否与查询范围有交集。
生成每分钟记录：对于有交集的压缩记录，生成每分钟的记录，并筛选出落在查询范围内的记录。
合并和排序结果：将所有符合条件的记录按时间升序排序后输出。

代码实现

C++

#include <iostream> #include <vector> #include <algorithm> using namespace std; struct Record { long long time; int value; }; bool compareRecords(const Record &a, const Record &b) { return a.time < b.time; } int main() { long long startQuery, endQuery; char comma; cin >> startQuery >> comma >> endQuery; int n; cin >> n; vector<Record> records; for (int i = 0; i < n; ++i) { long long start, end; int value; cin >> start >> comma >> end >> comma >> value; long long overlapStart = max(start, startQuery); long long overlapEnd = min(end, endQuery); if (overlapStart <= overlapEnd) { for (long long t = overlapStart; t <= overlapEnd; ++t) { records.push_back({t, value}); } } } if (records.empty()) { cout << -1 << endl; } else { sort(records.begin(), records.end(), compareRecords); for (const auto &record : records) { cout << record.time << "," << record.value << endl; } } return 0; }

C

#include <stdio.h> #include <stdlib.h> typedef struct { long long time; int value; } Record; int compareRecords(const void *a, const void *b) { Record *ra = (Record *)a; Record *rb = (Record *)b; return (ra->time > rb->time) - (ra->time < rb->time); } int main() { long long startQuery, endQuery; scanf("%lld,%lld", &startQuery, &endQuery); int n; scanf("%d", &n); Record *records = malloc(100 * sizeof(Record)); int count = 0; for (int i = 0; i < n; ++i) { long long start, end; int value; scanf("%lld,%lld,%d", &start, &end, &value); long long overlapStart = start > startQuery ? start : startQuery; long long overlapEnd = end < endQuery ? end : endQuery; if (overlapStart <= overlapEnd) { for (long long t = overlapStart; t <= overlapEnd; ++t) { records[count].time = t; records[count].value = value; count++; } } } if (count == 0) { printf("-1\n"); } else { qsort(records, count, sizeof(Record), compareRecords); for (int i = 0; i < count; ++i) { printf("%lld,%d\n", records[i].time, records[i].value); } } free(records); return 0; }

Python

start_query, end_query = map(int, input().split(',')) n = int(input()) records = [] for _ in range(n): start, end, value = map(int, input().split(',')) overlap_start = max(start, start_query) overlap_end = min(end, end_query) if overlap_start <= overlap_end: for t in range(overlap_start, overlap_end + 1): records.append((t, value)) if not records: print(-1) else: records.sort() for t, value in records: print(f"{t},{value}")

Java

import java.util.*; public class Main { public static void main(String[] args) { Scanner scanner = new Scanner(System.in); String[] queryRange = scanner.nextLine().split(","); long startQuery = Long.parseLong(queryRange[0]); long endQuery = Long.parseLong(queryRange[1]); int n = Integer.parseInt(scanner.nextLine()); List<Record> records = new ArrayList<>(); for (int i = 0; i < n; i++) { String[] parts = scanner.nextLine().split(","); long start = Long.parseLong(parts[0]); long end = Long.parseLong(parts[1]); int value = Integer.parseInt(parts[2]); long overlapStart = Math.max(start, startQuery); long overlapEnd = Math.min(end, endQuery); if (overlapStart <= overlapEnd) { for (long t = overlapStart; t <= overlapEnd; t++) { records.add(new Record(t, value)); } } } if (records.isEmpty()) { System.out.println(-1); } else { records.sort(Comparator.comparingLong(Record::getTime)); for (Record record : records) { System.out.println(record.getTime() + "," + record.getValue()); } } } static class Record { private long time; private int value; public Record(long time, int value) { this.time = time; this.value = value; } public long getTime() { return time; } public int getValue() { return value; } } }

JavaScript

const readline = require('readline'); const rl = readline.createInterface({ input: process.stdin, output: process.stdout }); let lines = []; rl.on('line', (line) => { lines.push(line); }).on('close', () => { const [startQuery, endQuery] = lines[0].split(',').map(Number); const n = parseInt(lines[1]); let records = []; for (let i = 2; i < 2 + n; i++) { const [start, end, value] = lines[i].split(',').map(Number); const overlapStart = Math.max(start, startQuery); const overlapEnd = Math.min(end, endQuery); if (overlapStart <= overlapEnd) { for (let t = overlapStart; t <= overlapEnd; t++) { records.push({ time: t, value: value }); } } } if (records.length === 0) { console.log(-1); } else { records.sort((a, b) => a.time - b.time); for (const record of records) { console.log(`${record.time},${record.value}`); } } });