1.事件模拟。
2.首先读取所有的汽车记录数据，筛选出合理的进入和离开时间，放到一个vector里面，对这个vector进行排序处理，进入时间早的放在前面。
3.对每一秒进行模拟，已经进入的车辆用一个小根堆进行存储维护，离开时间早的，排在堆顶。
3.取下一次进入校园车辆的时间，下一次离开校园车辆的时间，下一次查询的时间，取三者的最小值，直接跳那个时间点，进行处理，优化时间复杂度。
4.一开始第4个例子超时，后来采用了第3点中提到的优化方法，结果还是超时，考虑到查询量较大，于是把查询的cout改为printf，就通过了。
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。
1）最原始的一秒一秒进行模拟：
2）采用第3点的方法进行优化，还是超时
3）不进行时间事件模拟处理，仅输入数据，各测试点耗费时间：
4）最后把cout改为printf，通过：
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
AC代码：
//#include<string>
//#include <iomanip>
#include<vector>
#include <algorithm>
//#include<stack>
#include<set>
#include<queue>
#include<map>
//#include<unordered_set>
#include<unordered_map>
//#include <sstream>
//#include "func.h"
//#include <list>
#include<stdio.h>
#include<iostream>
#include<string>
#include<memory.h>
#include<limits.h>
using namespace std;
struct CarNode{
vector<pair<string, bool>> record;
vector<pair<string, string>> validRecord;
CarNode() :record(0), validRecord(0){};
};
struct RecordNode{
string id, in, out;
RecordNode() :id(""), in(""), out(""){};
RecordNode(string i,string a,string b) :id(i), in(a), out(b){};
};
bool cmpRecord(const pair<string, bool>&a, const pair<string, bool>&b)
{
return a.first < b.first;
}
bool cmpAllRecord(const RecordNode&a, const RecordNode&b)
{
return a.in < b.in;
}
int char2int(char a)
{
return a - '0';
}
int time2sec(string str)
{
return (char2int(str[0]) * 10 + char2int(str[1])) * 60*60 + (char2int(str[3]) * 10 + char2int(str[4])) * 60 + char2int(str[6]) * 10 + char2int(str[7]);
}
struct cmp
{
bool operator()(const RecordNode&a, const RecordNode&b)
{
return time2sec(a.out) > time2sec(b.out);
}
};
bool cmpPark(const pair<string, int>&a, const pair<string, int>&b)
{
if (a.second > b.second) return true;
else if (a.second == b.second&&a.first < b.first) return true;
else return false;
}
string sec2str(int a)
{
int hour = a / 3600;
int min = (a - hour * 3600) / 60;
int sec = a - hour * 3600 - min * 60;
char c1 = hour / 10 + '0';
char c2 = hour % 10 + '0';
string ans = "";
ans += c1;
ans += c2;
ans += ":";
c1 = min / 10 + '0';
c2 = min % 10 + '0';
ans += c1;
ans += c2;
ans += ":";
c1 = sec / 10 + '0';
c2 = sec % 10 + '0';
ans += c1;
ans += c2;
return ans;
}
int main(void)
{
int recordSum,querySum;
cin >> recordSum >> querySum;
map<string, CarNode> car;//建立car 哈希表
for (int i = 0; i < recordSum; i++)
{//输入记录
string id, time, flag;
cin >> id >> time >> flag;
//0为进入，1为出去
if (flag == "in")
car[id].record.push_back({ time, 0 });
else
car[id].record.push_back({ time, 1 });
}
vector<RecordNode> allRecord(0);
for (map<string, CarNode>::iterator ite = car.begin(); ite != car.end(); ite++)
{//筛选出有效记录，统一发到allRecord容器中
sort(ite->second.record.begin(), ite->second.record.end(), cmpRecord);
for (int i = 0; i < ite->second.record.size() - 1; i++)
{
if (!ite->second.record[i].second && ite->second.record[i + 1].second)
{//相邻的两条记录，第一条为进入，第二条为离开，则合理
allRecord.push_back(RecordNode(ite->first, ite->second.record[i].first, ite->second.record[i + 1].first));
}
}
}
//根据进入时间，对有效记录进行排序
sort(allRecord.begin(), allRecord.end(), cmpAllRecord);
//输入查询记录
vector<string> queryRecord(querySum);
for (int i = 0; i < querySum; i++)
{
cin >> queryRecord[i];
}
sort(queryRecord.begin(), queryRecord.end());
int parkCar = 0;
int next = 0;
int queryIdx = 0;
map<string, int> parkTime;
//优先队列，记录了在校园内的车，以离开时间大小建立小根堆
priority_queue<RecordNode, vector<RecordNode>, cmp> inCampus;
int maxTime = 0;
string maxID = "";
vector<pair<string, int>> maxTimeCar(0);
for (int i = 0; i < 24 * 3600; i++)
{
while (next<allRecord.size() && time2sec(allRecord[next].in) == i)
{//查看当前是否有车进入校园
inCampus.push(allRecord[next]);
next++;
parkCar++;
}
while (!inCampus.empty() && time2sec(inCampus.top().out) == i)
{//查看当前是否有车离开校园
//记录停车时间
parkTime[inCampus.top().id] += time2sec(inCampus.top().out) - time2sec(inCampus.top().in);
if (parkTime[inCampus.top().id] >= maxTime)
{
maxTimeCar.push_back({ inCampus.top().id, parkTime[inCampus.top().id] });
maxTime = parkTime[inCampus.top().id];
maxID = inCampus.top().id;
}
inCampus.pop();
parkCar--;
}
if (queryIdx<queryRecord.size() && time2sec(queryRecord[queryIdx]) == i)
{
queryIdx++;
printf("%d\n",parkCar);//刚开始采用了cout输出，结果超时，改为printf后不超时
}
int inTime = 24 * 3600, outTime = 24 * 3600, queryTime = 24 * 3600;
if (next < allRecord.size())//记录下一个需要处理的时间点
inTime = time2sec(allRecord[next].in);
if (!inCampus.empty())//记录下一个需要处理的时间点
outTime = time2sec(inCampus.top().out);
if (queryIdx < queryRecord.size())//记录下一个需要处理的时间点
queryTime = time2sec(queryRecord[queryIdx]);
int nextTime = min(min(inTime,outTime),queryTime);
i = nextTime - 1;//因为for循环里面有i++，所以这里不需要直接达到nextTime
}
//对最大停车的车辆数组进行排序
sort(maxTimeCar.begin(), maxTimeCar.end(), cmpPark);
for (int i = 0; i < maxTimeCar.size(); i++)
{
if (maxTimeCar[i].second == maxTime)
{//停车时间等于最大值，则输出
cout << maxTimeCar[i].first << " ";//输出ID
}
else//不等，则直接跳出循环
break;
}
cout << sec2str(maxTime) << endl;
return 0;
}
