https://www.acwing.com/problem/content/description/1587/
思路:
电话记录的模型,先筛选出所有符合要求的记录,之后按照题目要求做即可。
#include <iostream>
#include <cstring>
#include <algorithm>
#include <unordered_map>
#include <vector>using namespace std;struct Event
{int tm, status;bool operator< (const Event &t) const{return tm < t.tm;}
};int get(vector<Event>& ets)
{int res = 0;for (int i = 0; i < ets.size(); i += 2)res += ets[i + 1].tm - ets[i].tm;return res;
}int main()
{int n, m;scanf("%d%d", &n, &m);unordered_map<string, vector<Event>> cars;char id[10], status[10];for (int i = 0; i < n; i ++ ){int hh, mm, ss;scanf("%s %d:%d:%d %s", id, &hh, &mm, &ss, status);int t = hh * 3600 + mm * 60 + ss;int s = 0;if (status[0] == 'o') s = 1;cars[id].push_back({t, s});}vector<Event> events;for (auto& item : cars){auto& ets = item.second;sort(ets.begin(), ets.end());int k = 0;for (int i = 0; i < ets.size(); i ++ )if (ets[i].status == 0){if (i + 1 < ets.size() && ets[i + 1].status == 1){ets[k ++ ] = ets[i];ets[k ++ ] = ets[i + 1];i ++ ;}}ets.erase(ets.begin() + k, ets.end());for (int i = 0; i < k; i ++ ) events.push_back(ets[i]);}sort(events.begin(), events.end());int k = 0, sum = 0;while (m -- ){int hh, mm, ss;scanf("%d:%d:%d", &hh, &mm, &ss);int t = hh * 3600 + mm * 60 + ss;while (k < events.size() && events[k].tm <= t){if (events[k].status == 0) sum ++ ;else sum -- ;k ++ ;}printf("%d\n", sum);}int maxt = 0;for (auto& item : cars) maxt = max(maxt, get(item.second));vector<string> res;for (auto& item : cars)if (get(item.second) == maxt)res.push_back(item.first);sort(res.begin(), res.end());for (int i = 0; i < res.size(); i ++ ) printf("%s ", res[i].c_str());printf("%02d:%02d:%02d\n", maxt / 3600, maxt % 3600 / 60, maxt % 60);return 0;
}