AT_abc001_4 [ABC001D] 感雨時刻の整理 题解

题目理解

题目给出若干个时间段，格式为 HHMM-HHMM，要求：

1. 时间舍入：将每个时间段的开始时间向前调整到最近的5分钟整数倍，结束时间向后调整到最近的5分钟整数倍
2. 区间合并：将调整后重叠或相邻的时间段合并
3. 输出：按时间顺序输出合并后的时间段，格式同样为四位数字表示时分

舍入规则示例

• 1148 → 开始时间向前舍入到 1145（能被5整除）
• 1210 → 结束时间向后舍入到 1210（已是5的倍数，保持不变）
• 1323 → 结束时间向后舍入到 1325

解法一：离散化 + 差分数组

核心思想

由于一天只有24小时，时间分辨率是5分钟，因此可以用离散化的方法将时间转换为整数索引，使用差分数组维护区间覆盖，最后找出所有被覆盖的连续区间。

关键步骤

1. 时间转换函数

将 HHMM 格式的时间转换为以5分钟为单位的索引：

int toIndex(int t, int type) {
    // type = 1: 开始时间（向下取整）
    // type = 2: 结束时间（向上取整）
    int hour = t / 100;
    int minute = t % 100;
    int idx = hour * 12 + minute / 5;  // 每小时12个5分钟段
    if (type == 2 && minute % 5 != 0) {
        idx++;  // 结束时间向上取整
    }
    return idx;
}

为什么不直接使用分钟？ 因为舍入规则以5分钟为单位，将时间压缩为 24 × 12 = 288 个离散点，大大简化处理。

2. 处理区间相邻问题

一个重要的技巧：将索引乘以2，这样原本相邻但不重叠的区间（如 [1,2] 和 [3,4]）在乘以2后会变成 [2,4] 和 [6,8]，中间会有空隙，避免错误合并。

int l = toIndex(start, 1) * 2;
int r = toIndex(end, 2) * 2;
diff[l]++, diff[r + 1]--;

3. 完整代码

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;

const int N = 305 * 2;  // 288 * 2 足够大
int diff[N];

// 时间转换函数
int toIndex(int t, int isEnd) {
    int hour = t / 100;
    int minute = t % 100;
    int idx = hour * 12 + minute / 5;
    if (isEnd && minute % 5 != 0) {
        idx++;
    }
    return idx;
}

// 输出函数：将索引转换回 HHMM 格式
void printTime(int l, int r) {
    l /= 2; r /= 2;  // 除以2还原
    // 起始时间
    int startHour = l / 12;
    int startMin = (l % 12) * 5;
    // 结束时间
    int endHour = r / 12;
    int endMin = (r % 12) * 5;
    printf("%02d%02d-%02d%02d\n", startHour, startMin, endHour, endMin);
}

int main() {
    int n;
    cin >> n;
    
    // 差分数组维护区间覆盖
    for (int i = 0; i < n; i++) {
        int a, b;
        scanf("%d-%d", &a, &b);
        int l = toIndex(a, 0) * 2;
        int r = toIndex(b, 1) * 2;
        diff[l]++;
        diff[r + 1]--;
    }
    
    // 前缀和还原覆盖情况
    for (int i = 1; i <= 290 * 2; i++) {
        diff[i] += diff[i - 1];
    }
    
    // 提取连续被覆盖的区间
    int l = 0, r = 0;
    for (int i = 1; i <= 290 * 2; i++) {
        if (diff[i] && !l) {
            l = i;  // 区间开始
        }
        if (!diff[i] && l) {
            r = i - 1;  // 区间结束
            printTime(l, r);
            l = 0;
        }
    }
    
    return 0;
}

复杂度分析

• 时间复杂度：O(n + T)，其中 T = 288 × 2 ≈ 576
• 空间复杂度：O(T)

解法二：区间排序 + 贪心合并

核心思想

将每个时间段转换为标准区间后，按左端点排序，然后贪心地合并重叠或相邻的区间。

完整代码

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

const int M = 30005;
pair<int, int> intervals[M];

int toIndex(int t, int isEnd) {
    int hour = t / 100;
    int minute = t % 100;
    int idx = hour * 12 + minute / 5;
    if (isEnd && minute % 5 != 0) {
        idx++;
    }
    // 加1避免与0混淆，便于输出处理
    return idx + 1;
}

void printTime(int l, int r) {
    l--; r--;
    int startHour = l / 12;
    int startMin = (l % 12) * 5;
    int endHour = r / 12;
    int endMin = (r % 12) * 5;
    printf("%02d%02d-%02d%02d\n", startHour, startMin, endHour, endMin);
}

int main() {
    int n, m = 0;
    cin >> n;
    
    for (int i = 0; i < n; i++) {
        int a, b;
        scanf("%d-%d", &a, &b);
        intervals[++m] = {toIndex(a, 0), toIndex(b, 1)};
    }
    
    sort(intervals + 1, intervals + m + 1);
    
    int l = 0, r = 0;
    for (int i = 1; i <= m; i++) {
        if (l == 0) {
            l = intervals[i].first;
            r = intervals[i].second;
        }
        // 区间重叠或相邻则合并
        if (intervals[i + 1].first <= r) {
            r = max(r, intervals[i + 1].second);
        }
        if (intervals[i + 1].first > r) {
            printTime(l, r);
            l = 0;
        }
    }
    if (l) printTime(l, r);
    
    return 0;
}

复杂度分析

• 时间复杂度：O(n log n)
• 空间复杂度：O(n)

两种解法对比

注意事项

1. 相邻区间合并：题目要求合并相邻的区间（如 0005-0010 和 0010-0015 应合并为 0005-0015）。差分数组解法需要特殊处理（乘以2）才能正确合并相邻区间。

2. 输出格式：需要保证输出为4位数字，不足4位时前补0，使用 printf("%02d") 即可。

3. 边界处理：注意 2400 这个特殊时间点的处理，通常 2400 应视为第二天的 0000。