共计 3330 个字符，预计需要花费 9 分钟才能阅读完成。
题目粗心：
给出 N 条记录，每条记录给出一辆车的车牌号、以后时刻以及出入校状况 (入校(in) 还是出校 out))。而后给出 K 个查问，每个查问给出一个时刻，输入在这个时刻校园内的车辆数。查问结束后输入在学校内停留时间最长的车辆的车牌号 (如果有多个，就一并输入) 和
对应的停留时间。
算法思路：
该题和 1016 Phone Bills 的数据处理要求很类似，这里要求给定某一个时刻，要求以后时刻有多少辆车在停车场，最直观的想法就是用一个变量 (car_num) 来记录车辆数目，从开始时刻到查问时刻，遇到 in 的记录就加一，遇到 out 的时候就减一，而后就失去以后查问时刻有多少车辆存在停车场了，然而该应用办法有一个前提条件，那就是所有的记录都得是无效记录，然而这里的记录有可能是有效的，所以，第一件事就是将记录所有的无效记录全副筛选进去寄存在 valid_records 数组中，而后对于对于每一次查问就能够依照上述办法取得车辆数目，对于最长的停车工夫长度能够在筛选无效记录的时候记录最长的停车工夫和对应的车牌号码。
排序规定 1：
首先依照车牌号分组，依照字典序排序，对于车牌号雷同的依照工夫先后排序，这是为了筛选无效记录。排序规定 2：
依照工夫先后排序。筛选无效记录的办法：
先依照排序规定一进行排序, 应用指针 i 遍历所有的记录，这里的 i 最大为 N -2, 因为无效记录为一对，所以 i <N- 1 即可。首先得判断 i 和 i + 1 条记录为同一辆车的记录，否则无意义，而后再判断 i 和 i + 1 的 status 别离为 in 和 out，这样的记录才是一对无效记录，对于每一条无效记录，咱们将 i 和 i + 1 增加进 valid_records 数组中，而后再累计该车辆的停车工夫，这里应用 map<string,int> cars 进行存储每一辆车对应的累计停车工夫，
最初在记录最大的停车时长即可(用 max_parking_time 记录)
获取查问时刻停车场的车辆数目的办法：
先依照排序规定 2 排序，而后咱们留神到查问的时刻是顺次递增的，也就是说，如果每一次查问都是从都开始查问的话，会和上一次查问的记录反复，能够采取紧接着上一次查问地位往后查问车辆进出状况的办法，咱们应用 index 记录上一次查问的记录地位，初始为 0，应用 car_num 记录上一次查问停车场车辆的停留数目，只有以后 index 指向的记录的工夫 <= 查问工夫，那么就反复以下操作：
1、如果 index 指向记录的 status 为 in,car_num++;
2、如果 index 指向记录的 status 为 out,car_num--;留神:
1、对同一辆车来说，配对的 on 和 off 必须满足在把这辆车的记录按工夫顺序排列后，在它们之间不容许呈现其余 on 或者 off 的记录; 否则，将被视为有效记录。2、如果每一次查问都是从 00:00:00 开始查问的话，会超时。3、有可能查问工夫在所有记录时刻之后，比方查问为 23:59:59，然而记录的最靠后的工夫为 20:00:00, 那么 index 得判断是否将 valid_records 遍历结束了。测试点 1 和 2 考查该点(本人测试失去的后果，不肯定精确)
提交后果：
AC 代码：
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<string>
#include<vector>
#include<map>
using namespace std;
struct Record{
string plate_number ;// 车牌号码
int time;
bool status;// in 为 true,out 为 false
};
int getSeconds(int hh,int mm,int ss){return hh*3600+mm*60+ss;}
bool cmp(Record a,Record b){if(a.plate_number!=b.plate_number){return a.plate_number<b.plate_number;}else{return a.time<b.time;}
}
bool cmpByTime(Record a,Record b){return a.time<b.time;}
int main(){
int N,K;// 记录总数和查问总数
scanf("%d %d",&N,&K);
vector<Record> records;
Record record;
char plate_number[20];
int hh,mm,ss;
char status[10];
for(int i=0;i<N;++i){scanf("%s %d:%d:%d %s",plate_number,&hh,&mm,&ss,status);
record.plate_number = plate_number;
record.time = getSeconds(hh,mm,ss);
record.status = strcmp(status,"in")==0;
records.push_back(record);
}
sort(records.begin(),records.end(),cmp);
// 筛选有效记录
map<string,int> cars;// 每一辆车停车的最长工夫
int max_parking_time = -1;// 最长停车工夫
vector<Record> valid_records;
int begin=0,next=0;
for(int i=0;i<N-1;++i){if(records[i].plate_number==records[i+1].plate_number){
// i 和 i + 1 是同一辆车
if(records[i].status&&!records[i+1].status){
// i 为 in,i+ 1 为 out,i 与 i + 1 为一对无效记录
valid_records.push_back(records[i]);
valid_records.push_back(records[i+1]);
int parking_time = records[i+1].time-records[i].time;// 停车工夫
// 更新该辆车的累计停车工夫
cars[records[i].plate_number] += parking_time;
max_parking_time = max_parking_time<cars[records[i].plate_number]?cars[records[i].plate_number]:max_parking_time;// 更新所有车辆最长停车工夫
}
}
}
// 依据工夫进行排序
sort(valid_records.begin(),valid_records.end(),cmpByTime);
// 查问开始
int index = 0;// 以后查问记录的下标
int car_num = 0;// 以后停车场的车辆数目
for(int i=0;i<K;++i){scanf("%d:%d:%d",&hh,&mm,&ss);
int query_time = getSeconds(hh,mm,ss);
// 从 index 始终找到停车工夫大于 query_time 的后面一辆记录即可
while(index<valid_records.size()&&valid_records[index].time<=query_time){if(valid_records[index].status){++car_num;}else{--car_num;}
++index;
}
printf("%d\n",car_num);
}
// 输入最长停车工夫的车牌号和工夫
map<string,int>::iterator it;
for(it=cars.begin();it!=cars.end();++it){if(it->second==max_parking_time){printf("%s",it->first.c_str());
}
}
printf("%02d:%02d:%02d",max_parking_time/3600,max_parking_time%3600/60,max_parking_time%60);
return 0;
}
