PAT 三月 22, 2020

PAT甲级 1095 Cars on Campus (30分)

文章字数 6k 阅读约需 5 mins. 阅读次数 -

Zhejiang University has 8 campuses and a lot of gates. From each gate we can collect the in/out times and the plate numbers of the cars crossing the gate. Now with all the information available, you are supposed to tell, at any specific time point, the number of cars parking on campus, and at the end of the day find the cars that have parked for the longest time period.

Input Specification:

Each input file contains one test case. Each case starts with two positive integers N (≤ ${10^4}$), the number of records, and K (≤ $8×10^4$) the number of queries. Then N lines follow, each gives a record in the format:

plate_number hh:mm:ss status

where plate_number is a string of 7 English capital letters or 1-digit numbers; hh:mm:ss represents the time point in a day by hour:minute:second, with the earliest time being 00:00:00 and the latest 23:59:59; and status is either in or out.

Note that all times will be within a single day. Each in record is paired with the chronologically next record for the same car provided it is an out record. Any in records that are not paired with an out record are ignored, as are out records not paired with an in record. It is guaranteed that at least one car is well paired in the input, and no car is both in and out at the same moment. Times are recorded using a 24-hour clock.

Then K lines of queries follow, each gives a time point in the format hh:mm:ss. Note: the queries are given in ascending order of the times.

Output Specification:

For each query, output in a line the total number of cars parking on campus. The last line of output is supposed to give the plate number of the car that has parked for the longest time period, and the corresponding time length. If such a car is not unique, then output all of their plate numbers in a line in alphabetical order, separated by a space.

Sample Input:

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

Sample Output:

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

思路

  • 将时间统一转换为秒,方便比较;将 “in” 状态表示为1,“out” 状态表示为-1,方便停车数 cnt 的计算(即 cnt += status)
  • 将记录的结构体数组,根据先 id,后 time 的顺序进行排序。然后从中找出合法的记录,加入 vector,顺便用 map<string, int> 存储各个车辆的总停车时长,并记录最大中停车时长
  • 然后输入查询时间,每输入一个查询 id,就接着上次遍历这个 vector,一边遍历,一边计算当前停车数 cnt,直到当前时间大于查询时间,即可输出 cnt
  • 最后,再遍历一遍 map,输出所有等于 maxLen 的车辆 id(map 已根据 id 的字母顺序自动排序)

注意点

  • 最长停车时长(parked for the longest time period),指的是一辆车在一天中的总停车时长,而不是指某一次停车的时长
  • 如果一辆车多次 in,应该取最后一个 in 记录;如果一辆车多次 out,应该取第一个 out 记录
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include <map>
using namespace std;

const int maxn = 10000;

struct Record {
    char id[8];
    int time, status;
} records[maxn];

vector<Record> vec;
map<string, int> lenMap;

int cmpByIdAndTime(Record r1, Record r2) {
    int strCmp = strcmp(r1.id, r2.id);
    if (strCmp != 0) {
        return strCmp < 0;
    } else {
        return r1.time < r2.time;
    }
}

int cmpByTime(Record r1, Record r2) {
    return r1.time < r2.time;
}

int main() {
    int n, k, hour, min, sec, time, cnt = 0, maxLen = -1, j = 0;
    scanf("%d %d", &n, &k);
    char status[3];
    for (int i = 0; i < n; i++) {
        scanf("%s %d:%d:%d %s", records[i].id, &hour, &min, &sec, status);
        records[i].time = hour * 3600 + min * 60 + sec;
        if (strcmp(status, "in") == 0) {
            records[i].status = 1;
        } else {
            records[i].status = -1;
        }
    }
    sort(records, records + n, cmpByIdAndTime);
    for (int i = 1; i < n; i++) {
        if (strcmp(records[i].id, records[i - 1].id) == 0 && records[i - 1].status == 1 && records[i].status == -1) {
            vec.push_back(records[i - 1]);
            vec.push_back(records[i]);
            lenMap[records[i].id] += records[i].time - records[i - 1].time;
            if (lenMap[records[i].id] > maxLen) {
                maxLen = lenMap[records[i].id];
            }
        }
    }
    sort(vec.begin(), vec.end(), cmpByTime);
    for (int i = 0; i < k; i++) {
        scanf("%d:%d:%d", &hour, &min, &sec);
        time = hour * 60 * 60 + min * 60 + sec;
        while (j < vec.size() && vec[j].time <= time) {
            cnt += vec[j].status;
            j++;
        }
        printf("%d\n", cnt);
    }
    for (auto it : lenMap) {
        if (it.second == maxLen) {
            printf("%s ", it.first.c_str());
        }
    }
    printf("%02d:%02d:%02d", maxLen / 3600, maxLen % 3600 / 60, maxLen % 60);
    return 0;
}
0%