题意:给你一堆车的进出记录共N个(其中包含无效记录),再给K个询问,每一次给一个时间(时间是升序给出),输出此时有多少辆车在学校里,然后最后输出一下停车时间最长的车和它的时间,如果有多个,那么按字典序输出车牌号即可。
坑点:
- 一辆车可能会有多条进出记录,它的停车时间应该是合法等待时间之和
- 如果遇到一条out记录,则应当使用时间离他最近的那一条in记录来算停车时间
- sort函数的坑点:别用<=或>=
#include <iostream>
#include <string>
#include <algorithm>
#include <map>
#include <vector>
using namespace std;
#define PII pair<int, int>
const int N = 10010;
int n, k;
int h, m, s;
string id, flag;
struct node{
string id, flag;
int sec;
node(int h, int m, int s, string &a, string &b){
sec = h * 3600 + m * 60 + s;
id = a, flag = b;
}
bool operator<(const node &n) const{
return sec < n.sec;
}
};
map<string, int> park; // 停车时间
map<string, int> rec; // 筛选有效对
vector<PII> v; // 所有时间
vector<node> nodes; // 所有记录
int main(){
cin >> n >> k;
for(int i = 0; i < n; i ++){
cin >> id;
scanf("%d:%d:%d", &h, &m, &s);
cin >> flag;
nodes.push_back(node(h, m, s, id, flag));
}
sort(nodes.begin(), nodes.end());
for(int i = 0; i < nodes.size(); i ++){
if(nodes[i].flag == "in") rec[nodes[i].id] = i + 1;
else if(rec[nodes[i].id]){
int idx = rec[nodes[i].id] - 1;
rec[nodes[i].id] = 0;
park[nodes[i].id] += nodes[i].sec - nodes[idx].sec;
v.push_back({nodes[idx].sec, 0});
v.push_back({nodes[i].sec, 1});
}
}
sort(v.begin(), v.end());
// 这里由于车的进出时间和询问时间均为升序,所以没有必要每一次询问都重新循环
int cnt = 0, idx = 0;
while(k --){
scanf("%d:%d:%d", &h, &m, &s);
int sec = h * 3600 + m * 60 + s;
for(; idx < v.size(); idx ++){
if(sec >= v[idx].first)
if(v[idx].second) cnt --;
else cnt ++;
else break;
}
cout << cnt << endl;
}
int maxv = 0;
for(auto p : park) maxv = max(maxv, p.second);
for(auto p : park) if(p.second == maxv) cout << p.first << ' ';
h = maxv / 3600, m = (maxv - h * 3600) / 60, s = maxv - h * 3600 - m * 60;
printf("%02d:%02d:%02d", h, m, s);
return 0;
}