文章目录
题目
题目翻译
题目描述
原文
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.
翻译
浙江大学有6个校区和很多大门。 我们可以从每个闸门收集进出闸门的汽车的进出时间和车牌号。 现在有了所有可用的信息，您应该告诉在任何特定时间点校园内停车的汽车数量，并在一天结束时找到停放时间最长的汽车。
输入描述
原文
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.
翻译
每个输入文件包含一个测试用例。每个案例以两个正整数 N (<= 10000)->记录数 和 K (<= 80000)->查询数 开始。然后 N 行，每行的输入格式为：
车牌号 hh:mm:ss 状态
其中plate_number为7个英文大写字母或1位数字的字符串； hh:mm:ss 以小时:分钟:秒表示一天中的时间点，最早时间为00:00:00，最晚时间为23:59:59；状态为 in 或 out。
请注意，所有时间都将在一天之内。**每个“in”记录与同一辆车的按时间顺序排列的下一个记录配对，但是它必须是“out”记录。任何未与“out”记录配对的“in”记录都将被忽略，与“in”记录未配对的“out”记录也将被忽略。**保证至少有一辆车在输入中配对良好，并且没有一辆车同时“in”和“out”。时间记录使用 24 小时制。
然后是 K 行查询，每行以 hh:mm:ss 格式给出一个时间点。注：查询按时间升序排列。
输出描述
原文
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.
翻译
对于每个查询，在一行中输出在校园内停车的汽车总数。输出的最后一行应该是停车时间最长的车辆的车牌号，以及相应的时间长度。如果这样的车不是唯一的，那么按字母顺序输出所有的车牌号，用空格隔开。
题目大意总结
- 题目大意：给出n个车牌号、时间点、进出状态的记录，然后查询k个时间点这时校园内的车辆个数。最后还要输出在校园里面呆的时间最长的车的车牌号，以及呆了多久的时间。如果有多辆车就按照它的字母从小到大输出车牌。
配对要求是，如果一个车多次进入未出，取最后一个值；如果一个车多次out未进入，取第一个值。 - 注意：一个车可能出入校园好多次，停车的时间应该取之和。
这最后一句话，尤为关键，我疯狂调试就是败在这，一定是该车子在该天的所有停车时间的总和。
解题思路
- 既然是区间询问问题，我们很快想到线段树，但很明显，这道题的区间长度并不长，我们用差分就可以实现。我选择用差分，差分既简单又好用。
不了解差分的可以看看我之前对差分的详解–差分经典题目详解
额外的处理，我用哈希表对每个汽车牌子和它的进出时间进行一个映射，后面再把进出根据时间排序，取出两个挨着的进出时间即可，然后利用差分更新数组，在这个过程中也可以更新很多其他的变量，比如差分的左/右边界，又比如把每个汽车的停车总时间记录下来，最后再排序输出即可。
解题代码拆解
基本变量
int N, K;
unordered_map<string, vector<pair<int, int>>> mp; //存储所有的映射关系
vector<pair<int, string>> res; //存储答案映射关系的数组，根据停车时间排序即可
ll memo[MaxN * 3600 + 5]; //差分数组
solve函数处理时间格式转为整数方便计算 or scanf直接用分隔符得出数据
solve函数处理
ll solve(string& s) {
int state = 1;
int sz = s.size();
ll sum = 0, res = 0;
for (int i = 0; i < sz; i++) {
if (s[i] == ':') {
if (state == 1) {
res += sum * 3600;
} else if (state == 2) {
res += sum * 60;
}
sum = 0;
state++;
continue;
}
sum = 10 * sum + (s[i] - '0');
}
return res + sum;
}
scanf分隔符处理
scanf("%s %d:%d:%d %s\n", record[i].id, &h, &m, &s, temp);
update函数遍历哈希表更新差分数组和res数组
void update() {
int mn = INT_MAX, mx = INT_MIN;
for (auto && it : mp) {
sort(it.second.begin(), it.second.end());
int sz = it.second.size();
int sum_time = 0;
for (int i = 0; i < sz - 1; i++) {
if (it.second[i].second == 1 && it.second[i + 1].second == 0) {
mn = min(mn, it.second[i].first);
mx = max(mx, it.second[i + 1].first);
sum_time += it.second[i + 1].first - it.second[i].first;
memo[it.second[i].first]++;
memo[it.second[i + 1].first]--;
i++;
}
}
res.push_back(make_pair(sum_time, it.first));
}
for (int i = mn + 1; i <= mx + 1; i++) {
memo[i] += memo[i - 1];
}
}
Input_output函数负责输入与输出
void Input_output() {
ios::sync_with_stdio(false);
cin >> N >> K;
int c1 = N;
while (c1--) {
string s1, s2, s3;
cin >> s1 >> s2 >> s3;
int time = solve(s2);
int flag = s3 == "in" ? 1 : 0;
mp[s1].push_back(make_pair(time, flag));
}
update();
int c2 = K;
//K次询问K次输出
while (c2--) {
string s;
cin >> s;
int time = solve(s);
cout << memo[time] << '\n';
}
//最后的一行输出处理，由于排序从小到大，所以先找到最左
sort(res.begin(), res.end());
int nums = res.back().first;
int start = res.size() - 1;
while (start >= 0 && res[start].first == nums)
start--;
for (int i = start + 1; i < res.size(); i++) {
cout << res[i].second << ' ';
}
cout << to_time(nums);
}
整合函数得到答案
#include <bits/stdc++.h>
#define MaxN 24
using ll = long long;
using namespace std;
int N, K;
unordered_map<string, vector<pair<int, int>>> mp;
vector<pair<int, string>> res;
ll memo[MaxN * 3600 + 5];
string to_time(int x) {
int h = x / 3600;
x -= (h * 3600);
int m = x / 60;
x -= (m * 60);
int s = x;
string res = "";
stringstream ss;
if (h < 10)
ss << '0';
ss << h << ':';
if (m < 10)
ss << '0';
ss << m << ':';
if (s < 10)
ss << '0';
ss << s;
ss >> res;
return res;
}
ll solve(string& s) {
int state = 1;
int sz = s.size();
ll sum = 0, res = 0;
for (int i = 0; i < sz; i++) {
if (s[i] == ':') {
if (state == 1) {
res += sum * 3600;
} else if (state == 2) {
res += sum * 60;
}
sum = 0;
state++;
continue;
}
sum = 10 * sum + (s[i] - '0');
}
return res + sum;
}
void update() {
int mn = INT_MAX, mx = INT_MIN;
for (auto && it : mp) {
sort(it.second.begin(), it.second.end());
int sz = it.second.size();
int sum_time = 0;
for (int i = 0; i < sz - 1; i++) {
if (it.second[i].second == 1 && it.second[i + 1].second == 0) {
mn = min(mn, it.second[i].first);
mx = max(mx, it.second[i + 1].first);
sum_time += it.second[i + 1].first - it.second[i].first;
memo[it.second[i].first]++;
memo[it.second[i + 1].first]--;
i++;
}
}
res.push_back(make_pair(sum_time, it.first));
}
for (int i = mn + 1; i <= mx + 1; i++) {
memo[i] += memo[i - 1];
}
}
void Input_output() {
ios::sync_with_stdio(false);
cin >> N >> K;
int c1 = N;
while (c1--) {
string s1, s2, s3;
cin >> s1 >> s2 >> s3;
int time = solve(s2);
int flag = s3 == "in" ? 1 : 0;
mp[s1].push_back(make_pair(time, flag));
}
update();
int c2 = K;
while (c2--) {
string s;
cin >> s;
int time = solve(s);
cout << memo[time] << '\n';
}
sort(res.begin(), res.end());
int nums = res.back().first;
int start = res.size() - 1;
while (start >= 0 && res[start].first == nums)
start--;
for (int i = start + 1; i < res.size(); i++) {
cout << res[i].second << ' ';
}
cout << to_time(nums);
}
int main() {
Input_output();
return 0;
}