《Registration Day》题目分析

本题是一道非常复杂的模拟题。不仅需要模拟整个注册过程，还需要利用优先队列等数据结构减少时间复杂度。

冷静分析之后可以发现整个注册过程中有三种事件：

1)某位同学到达某个Office

2)某位同学进入某个Office开始办理手续

3)某位同学办完手续离开某个Office

一种事件发生后可能会出发另一种事件。例如：

某位同学到达某个Office(1类事件)，如果当前Office空闲，那么会触发这位同学在这个Office开始办理手续的事件(2类事件)。

而2类也会触发相应的3类事件。

3类事件会触发：(1)该同学到达下一个Office (2)另一位同学进入该Office开始办理手续。

我们可以把所有事件都放在优先队列里(按时间排序，时间相同按学生学号排序)，模拟的过程就是处理队首事件，同时将新产生的事件加入队列的过程。

基本思路是：

while(事件队列不为空):
    e = 队首事件
    if e 是1类事件:
        if e.office当前空闲且等待队列为空:
            新事件 e2 = e.student在e.office开始办理手续，时间e.time
            e2加入事件队列
        else:
            将e.student加入e.office的等待队列
    if e 是2类时间:
        e.office标记为不空闲
        新事件 e2 = e.student离开e.office，时间e.time + 办理时间
        e2加入事件队列
    if e 是3类事件:
        e.office标记为空闲
        if e.student 后面还有手续要办:
            新事件 e3 = e.student到达e.student.next_office(e.office)，时间e.time + K  
            e3加入事件队列
        else:
            记录e.student的完成时间
        if e.office的等待队列不为空
            student = 等在e.office的队首同学(到达最早，学号最小)
            新事件 e4 = student进入e.office开始办理手续，时间e.time
            e4加入事件队列

在基本思路的基础上可以有一些优化，让程序更简单。比如我们可以只记录1类事件，省略23类事件，即模拟时一个1类事件直接产生下一个1类事件(该同学到达下一个Office)。

这要求我们再额外记录一个数据，就是每个office最早的空闲时间：

while(事件队列不为空):
    e = 队首事件
    start_time = max(e.time, e.office最早空闲时间)
    finish_time = e.time + 办理时间
    e.office最早空闲时间 = finish_time  
    if e.student 后面还有手续要办:
        新事件 e2 = e.student到达e.student.next_office(e.office)，时间finish_time + K    
        e2加入事件队列  
    else:
        记录e.student的完成时间finish_time