九月月赛 T7 题解

由于最多只有

1440

个事件，所以医生和病人的数量都不会超过

1440

。

对于一个给定的

24

时制时刻，可以将它转化为

60 \times h + m

，表示这是一天中的第几分钟。可以简化后续的计算。

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

遇到挂号操作时，在数组中加入该病人。遇到签到操作时，判断病人是否存在，并且未签到过。若当前时刻晚于治疗时间前

60

分钟，则签到成功，更新对应的数组。

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

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

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

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

时间复杂度

\mathcal O(T^2)

。运用一些 STL 的技巧可以做到

\mathcal O(T\log T)

。

CPP

#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;
}

文章操作

相关推荐

评论

九月月赛 T7 题解