九月月赛 T7 题解

· · 题解

由于最多只有 1440 个事件，所以医生和病人的数量都不会超过 1440。

对于一个给定的 24 时制时刻，可以将它转化为 60 \times h + m，表示这是一天中的第几分钟。可以简化后续的计算。

每个病人只会挂号一次，所以开一个数组记录当前所有挂号过的病人以及病人的治疗时间，同时记录该病人是否已经成功签到过。

遇到挂号操作时，在数组中加入该病人。遇到签到操作时，判断病人是否存在，并且未签到过。若当前时刻晚于治疗时间前 60 分钟，则签到成功，更新对应的数组。

接下来考虑如何维护医生的治疗队列。同样用一个数组记录所有医生，并且对于每个医生开两个队列，分别表示未迟到队列和迟到队列。

若要将病人插入未迟到队列，由于插入之前的队列是有序的，这里可以用插入排序的思想：先将病人放到队列末尾，再依次 swap 到正确的位置。这里可以在结构体内重载小于运算符方便判断。

若要将病人插入迟到队列，由于迟到的病人按照签到时间排序，事件也按照时间顺序发生，所以直接放到迟到队列末尾即可。

发生叫号事件时，找到对应的医生。由于未迟到的病人总是在迟到的病人前，所以先判断未迟到队列有无病人，没有则再看迟到队列有无病人。若均没有病人，输出 No patient，否则取出对应队列的队列首，按照题述要求加密输出即可。

时间复杂度 \mathcal O(T^2)。运用一些 STL 的技巧可以做到 \mathcal O(T\log T)。

#include <bits/stdc++.h>
using namespace std;
int T;

struct node {
    int m;
    string s;
    int tm;

    bool operator < (const node &p) const {
        if (m != p.m) return m < p.m;
        return tm < p.tm;
    }
};

void print(string s) {
    int len = s.size();
    for (int i = 1; i < len - 1; ++i) s[i] = '*';
    cout << s << '\n';
}

string pname[1500];
node pdat[1500]; int pcnt, vis[1500];

string dname[1500];
node qu1[1500][1500], qu2[1500][1500];
int dcnt, qlen1[1500], qlen2[1500];

bool solve_reg(int nm) {
    string name; cin >> name;
    int pos = -1;
    for (int i = 1; i <= pcnt; ++i) {
        if (pname[i] == name && !vis[i]) {
            pos = i;
            break;
        }
    }
    if (pos == -1) return false;
    node pat = pdat[pos];
    int d = pat.m - nm;
    if (d > 60) return false;
    vis[pos] = 1;
    int dpos = -1;
    for (int i = 1; i <= dcnt; ++i) if (dname[i] == pat.s) {
        dpos = i;
        break;
    }
    if (dpos == -1) {
        dname[dpos = ++dcnt] = pat.s;
    }
    if (d >= 0) {
        qu1[dpos][++qlen1[dpos]] = node{pat.m, name, pat.tm};
        for (int i = qlen1[dpos]; i > 1 && qu1[dpos][i] < qu1[dpos][i - 1]; --i) swap(qu1[dpos][i], qu1[dpos][i - 1]);
    } else {
        qu2[dpos][++qlen2[dpos]] = node{nm, name};
    }
    return true;
}

int main() {
    cin >> T;
    while (T--) {
        string opt; int nh, nm;
        cin >> nh >> nm >> opt;
        nm += nh * 60;
        if (opt[0] == 'a') {
            string name, doc; int th, tm;
            cin >> name >> doc >> th >> tm;
            tm += th * 60;
            pname[++pcnt] = name;
            pdat[pcnt] = {tm, doc, nm};
        } else if (opt[0] == 'r') {
            if (solve_reg(nm)) puts("Success");
            else puts("Fail");
        } else {
            string doc;
            cin >> doc;
            int pos = -1;
            for (int i = 1; i <= dcnt; ++i) {
                if (dname[i] == doc) {
                    pos = i;
                    break;
                }
            }
            if (qlen1[pos]) {
                print(qu1[pos][1].s);
                --qlen1[pos];
                for (int i = 1; i <= qlen1[pos]; ++i) {
                    swap(qu1[pos][i], qu1[pos][i + 1]);
                }
            } else if (qlen2[pos]) {
                print(qu2[pos][1].s);
                --qlen2[pos];
                for (int i = 1; i <= qlen2[pos]; ++i) {
                    swap(qu2[pos][i], qu2[pos][i + 1]);                 
                }
            } else puts("No patient");
        }
    }
    return 0;
}