1 条题解
-
0
数据结构设计: TimeNode 结构体:封装日期时间,重载比较运算符以支持排序。 set:存储所有用户日程的起止时间点,自动去重并排序。 vector<pair<TimeNode, TimeNode>>:存储每个用户的日程区间。 区间预处理: 读取所有用户的日程区间,将起止时间点存入 set 中。 set 自动去重并排序,生成时间轴上的所有关键点。 空闲区间检测: 遍历时间轴上的所有相邻关键点形成的区间,检查: 覆盖条件:是否至少 n-1 个用户在此区间内空闲。 时长条件:区间长度是否至少 1 小时。 区间合并与输出: 合并连续满足条件的区间,输出最终结果。
#include <iostream> #include <iomanip> #include <cstring> #include <vector> #include <set> using namespace std; struct TimeNode { int year, month, day; int hour, minute, second; TimeNode() {} TimeNode(int a, int b, int c, int d, int e, int f) { year = a; month = b; day = c; hour = d; minute = e; second = f; } TimeNode(int *a) { year = a[0]; month = a[1]; day = a[2]; hour = a[3]; minute = a[4]; second = a[5]; } TimeNode operator=(const TimeNode &b) { year = b.year; month = b.month; day = b.day; hour = b.hour; minute = b.minute; second = b.second; } bool operator<(const TimeNode &b) const { if (year != b.year)return year < b.year; if (month != b.month)return month < b.month; if (day != b.day)return day < b.day; if (hour != b.hour)return hour < b.hour; if (minute != b.minute)return minute < b.minute; return second < b.second; } bool operator>(const TimeNode &b) const { return b < *this; } bool operator<=(const TimeNode &b) const { return !(b < *this); } bool operator>=(const TimeNode &b) const { return !(*this < b); } bool operator==(const TimeNode &b) const { return !(b < *this || *this < b); } bool operator!=(const TimeNode &b) const { return b < *this || *this < b; } void Output() { cout << setw(2) << setfill('0') << month << '/'; cout << setw(2) << setfill('0') << day << '/'; cout << setw(4) << setfill('0') << year << ' '; cout << setw(2) << setfill('0') << hour << ':'; cout << setw(2) << setfill('0') << minute << ':'; cout << setw(2) << setfill('0') << second; } }; int n; set<TimeNode> s; vector<TimeNode> Node; vector<pair<TimeNode, TimeNode> > A[22], Ans; //清空函数 void clr(int n) { s.clear(); Ans.clear(); Node.clear(); for (int i = 0; i <= n; ++i)A[i].clear(); } bool checkPer(int id, TimeNode l, TimeNode r) { for (int i = 0; i < A[id].size(); ++i) { if (l >= A[id][i].first && r <= A[id][i].second)return 0; } return 1; } bool check(TimeNode l, TimeNode r) { int tot = 0; for (int i = 1; i <= n; ++i) { if (checkPer(i, l, r))++tot; } return (tot >= n - 1 && tot >= 2); } bool checkLen(TimeNode l, TimeNode r) { if (r.year - l.year >= 2)return 1; r.month += (r.year - l.year) * 12; if (r.month - l.month >= 2)return 1; r.day += (r.month - l.month) * 30; if (r.day - l.day >= 2)return 1; r.hour += (r.day - l.day) * 24; if (r.hour - l.hour >= 2)return 1; r.minute += (r.hour - l.hour) * 60; r.second += (r.minute - l.minute) * 60; if (r.second - l.second >= 3600)return 1; return 0; } int main() { ios::sync_with_stdio(0); TimeNode Begin(1800, 1, 1, 0, 0, 0), End(2200, 1, 1, 0, 0, 0); int _; cin >> _; for (int sce = 1; sce <= _; ++sce) { cin >> n; clr(n); s.insert(Begin); s.insert(End); for (int i = 1; i <= n; ++i) { int m; cin >> m; for (int j = 1; j <= m; ++j) { int a[10], b[10]; for (int k = 0; k < 6; ++k)cin >> a[k]; for (int k = 0; k < 6; ++k)cin >> b[k]; string str; //没用 getline(cin, str); TimeNode l(a), r(b); A[i].push_back(make_pair(l, r)); s.insert(l); s.insert(r); } } for (set<TimeNode>::iterator it = s.begin(); it != s.end(); ++it) { Node.push_back(*it); } int l = 0, r = 0, cnt = Node.size(); cout << "Scenario #" << sce << ":\n"; while (l < cnt && r < cnt) { if (r >= cnt) break; while (r < cnt - 1 && check(Node[r], Node[r + 1]))++r; if (checkLen(Node[l], Node[r]))Ans.push_back(make_pair(Node[l], Node[r])); l = r + 1; while (l < cnt - 1 && !check(Node[l], Node[l + 1]))++l; r = l; } if (Ans.size() == 0)cout << "no appointment possible\n"; else { for (int i = 0; i < Ans.size(); ++i) { cout << "appointment possible from "; Ans[i].first.Output(); cout << " to "; Ans[i].second.Output(); cout << '\n'; } } cout << endl; } return 0; }
- 1
信息
- ID
- 961
- 时间
- 1000ms
- 内存
- 256MiB
- 难度
- 10
- 标签
- 递交数
- 1
- 已通过
- 1
- 上传者