1 条题解

  • 0
    @ 2025-5-4 14:28:13

    数据结构设计: 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
    上传者