题目描述

浙江大学有 8 个校区和许多大门。

从每个大门处我们都可以收集到进出这个大门的汽车的车牌号以及具体进出时间。

现在，给定你所有的有用信息，你需要做的是：

对于一些查询，计算出查询时刻校园内的汽车数量。
在一天结束时，找到在校园内停放时间最长的汽车。

输入格式

第一行包含两个整数，N 表示记录数量，K 表示查询时刻数量。

接下来 N 行，每行包含一条记录信息，格式如下：

plate_number hh:mm:ss status

plate_number（车牌号）是一个长度为 7 的只包含大写字母和数字的字符串，hh:mm:ss以 小时:分钟:秒 表示一天中的时间点，最早的时间为 00:00:00，最晚的时间为 23:59:59，status（状态）为 in 或 out。

注意，所有记录都在一天内产生。

每个 in 记录都与按时间顺序排列的同一辆车的下一条记录配对，但前提是这条记录是 out。

所有未与 out 记录配对的 in 记录以及未与 in 记录配对的 out 记录都必须忽略。

确保至少有一辆汽车能够成功配对，不会出现一辆车在同一时刻又进又出的情况。

使用24小时制记录时间。

接下来 K 行，每行包含一个查询时刻，形如 hh:mm:ss。

注意，查询时刻是按时间升序给出的。

输出格式

对于每个查询，请在一行中输出校园内停车的汽车总数。

注意：对于每个查询的时刻，先处理在该时刻所有的车辆进出事件，处理完之后再统计停在校园内的汽车数量。

输出的最后一行应给出停车时间最长的汽车的车牌号，以及相应的时间长度。

如果这样的汽车不唯一，则按照字典序依次输出所有车牌号，然后输出相应的时间长度，车牌号以及时间之间用空格隔开。

数据范围

1≤N≤104,
1≤K≤8×104

样例

输入样例：

16 7
JH007BD 18:00:01 in
ZD00001 11:30:08 out
DB8888A 13:00:00 out
ZA3Q625 23:59:50 out
ZA133CH 10:23:00 in
ZD00001 04:09:59 in
JH007BD 05:09:59 in
ZA3Q625 11:42:01 out
JH007BD 05:10:33 in
ZA3Q625 06:30:50 in
JH007BD 12:23:42 out
ZA3Q625 23:55:00 in
JH007BD 12:24:23 out
ZA133CH 17:11:22 out
JH007BD 18:07:01 out
DB8888A 06:30:50 in
05:10:00
06:30:50
11:00:00
12:23:42
14:00:00
18:00:00
23:59:00

输出样例：

1
4
5
2
1
0
1
JH007BD ZD00001 07:20:09

算法1

C++ 代码

#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;

const int MAXN = 10010;

struct Car
{
    char id[8];
    int time;
    char state[4];
    bool flag = false;
    int sum_time;
} car[MAXN];

int stop_num[86400] = {0};

bool cmp1(Car a, Car b)
{
    if (strcmp(a.id, b.id) == 0) return a.time < b.time;
    else return strcmp(a.id, b.id) < 0;
}

bool cmp2(Car a, Car b)
{
    if (a.flag != b.flag) return a.flag > b.flag;
    else return strcmp(a.id, b.id) < 0;
}

bool cmp3(Car a, Car b)
{
    if(a.sum_time != b.sum_time) return a.sum_time > b.sum_time;
    else return strcmp(a.id, b.id) < 0;
}

int main()
{
    int N, K;
    cin >> N >> K;

    for (int i = 0; i < N; i ++)
    {
        int h, m, s;
        scanf("%s %d:%d:%d %s", car[i].id, &h, &m, &s, car[i].state);
        car[i].time = h * 3600 + m * 60 + s;
    }

    sort(car, car + N, cmp1);

    for (int i = 1; i < N; i ++)
    {
        if (strcmp(car[i].id, car[i - 1].id) == 0 && 
            strcmp(car[i - 1].state, "in") == 0 && strcmp(car[i].state, "out") == 0)
        {
            car[i].sum_time = car[i].time - car[i - 1].time;
            for (int j = car[i - 1].time; j < car[i].time; j ++)
            {
                stop_num[j] ++;
            }
            car[i].flag = true;
            i ++;
        }
    }

    while (K --)
    {
        int h, m, s, time;
        scanf("%d:%d:%d", &h, &m, &s);
        time = h * 3600 + m * 60 + s;
        printf("%d\n", stop_num[time]);
    }

    sort(car, car + N, cmp2);

    for (int i = 1; car[i].flag; i ++)
    {
        if (strcmp(car[i].id, car[i - 1].id) == 0)
        {
            car[i].sum_time += car[i - 1].sum_time;
            car[i - 1].flag = false; 
        }
    }

    sort(car, car + N, cmp3);

    printf("%s ", car[0].id);
    for (int i = 1; car[i].sum_time == car[i - 1].sum_time; i ++)
    {
        printf("%s ", car[i].id);
    }

    int h, m, s, time = car[0].sum_time;
    h = time / 3600;
    m = (time % 3600) / 60;
    s = time % 60;

    printf("%02d:%02d:%02d", h, m, s);
    return 0;
}