Zhejiang University has 6 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 (<= 10000), the number of records, and K (<= 80000) 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
题目大意：停车场登记表里面又若干条顺序错乱的记录，要求把错误的记录去除（进入和出来无法配对的、只有出没有进、进了后再也没出来的，都算错误），然后对于给出若干条升序的时间，输出当时停车场里面有多少车。
首先，在时间存储上建议使用时间戳的形式，将时间化为秒数来存储，在排序和判断事容易判断
在去除无用数据时，可以先对车牌进行排序，将车牌一样的记录放在一起，同时对时间进行排序，使得同样车牌按照时间进行排序，排序后的数组长这样：
DB8888A 23450 1
DB8888A 46800 0
JH007BD 18599 1
JH007BD 18633 1
JH007BD 44622 0
JH007BD 44663 0
JH007BD 64801 1
JH007BD 65221 0
ZA133CH 37380 1
ZA133CH 61882 0
ZA3Q625 23450 1
ZA3Q625 42121 0
ZA3Q625 86100 1
ZA3Q625 86390 0
ZD00001 14999 1
ZD00001 41408 0这样，前后时同一辆车，并且前进后出，这样的记录就是合法的，将其存放到correct数组里面。
correct数组应该是这样：
DB8888A 23450 1
DB8888A 46800 0
JH007BD 18633 1
JH007BD 44663 0
JH007BD 64801 1
JH007BD 65221 0
ZA133CH 37380 1
ZA133CH 61882 0
ZA3Q625 23450 1
ZA3Q625 42121 0
ZA3Q625 86100 1
ZA3Q625 86390 0
ZD00001 14999 1
ZD00001 41408 0得到了合法的记录后，在判断每时每刻有多少车在停车场，我们绝对不可以一遍遍去遍历，否则有两个测试点会超时，由于给出的查询数据是升序的，我们使用一个计数器来模拟车辆进出，然后来计算。
最后，计算那辆车停留时间最长时，直接使用map存储车牌号以及停车时间即可，要注意停车时间可能由多个部分组成。
代码如下：
#include <iostream>
#include <vector>
#include <string>
#include <map>
#include <algorithm>
#include <cstdio>
using namespace std;
typedef struct {
string id;
int time;
bool status;
} lognode;
vector<lognode> Log, correct;
/*
车牌号和时间排序方法
*/
bool cmp_id_time(lognode a, lognode b){
if(a.id==b.id)
return a.time < b.time;
else return a.id < b.id;
}
/*
仅排序时间
*/
bool cmp_time(lognode a, lognode b){
return a.time < b.time;
}
int main(){
int N, K;
map<string, int> mp;
cin >> N >> K;
for(int i = 0; i < N; i++){
string id, stat;
int time, hh, mm, ss;
bool status;
cin >> id;
scanf("%2d:%2d:%2d", &hh, &mm, &ss);
time = ((hh*60)+mm)*60+ss;
cin >> stat;
status = stat == "in" ? true : false;
Log.push_back({id, time, status});
}
sort(Log.begin(), Log.end(), cmp_id_time);
for(vector<lognode>::iterator it = Log.begin(); it < Log.end()-1; it++){
vector<lognode>::iterator next = it + 1;
if(it->id == next->id && it->status && !next->status){
correct.push_back(*it);
correct.push_back(*next);
int d_time = next->time - it->time;
mp[it->id] += d_time;
}
}
//debug
/*for(vector<lognode>::iterator it = correct.begin(); it < correct.end(); it++){
printf("%s\t%d\t%d\n", it->id.c_str(), it->time, it->status);
}*/
sort(correct.begin(), correct.end(), cmp_time);
int now = 0, carCnt = 0;
for(int i = 0; i < K; i++){
int time, hh, mm, ss;
scanf("%2d:%2d:%2d", &hh, &mm, &ss);
time = ((hh*60)+mm)*60+ss;
while(now<correct.size() && correct[now].time <= time){
if(correct[now].status) carCnt++; //车进入
else carCnt--; //车出去
now++; //移动到下一跳记录
}
cout << carCnt << endl;
}
vector<string> maxId;
int maxTime = 0;
for(map<string, int>::iterator it = mp.begin(); it != mp.end(); it++){
if(it->second > maxTime){
maxTime = it->second;
maxId.clear();
maxId.push_back(it->first);
}
else if(it->second == maxTime)
maxId.push_back(it->first);
}
sort(maxId.begin(), maxId.end());
for(int i = 0; i < maxId.size(); i++)
cout << maxId[i] << ' ';
printf("%02d:%02d:%02d\n", maxTime/60/60, maxTime%3600/60, maxTime%60);
return 0;
}