UVa 10588

Queuing at the doctors

from Chapter 3. Data Structures :: Fundamental Data Structures :: Exercises: Beginner

Problem

某公司要求每个员工都必须到当地的医院体检，并给每个员工安排了体检的顺序。为了节约等待时间，员工们被要求分时段去体检，但排队仍然是必不可少的。因此，公司制定了下面几条规定：

• 员工的编号从1到n。
• 员工在规定的时间点上一定准时到达医院开始体检。
• 员工有自己的体检顺序，并且一定按顺序来体检，直到体检完才离开医院。
• 当有多个员工在同一个时刻到同一个医生那体检时，编号小的优先，其他人按到达的先后顺序和编号大小排队等待。

已经知道每个医生在每单位1的时间内可以检查一个员工，给定所有员工的体检时间和体检顺序，请计算一下最后一个员工离开医院的时间。

一共有N（1 ≤ N ≤ 1000）个员工，M（1 ≤ M ≤ 1000）个医生，所有人总的检查次数不超过1000000次。

Solution

排队有很明显的优先规则：先到的优先，同时到的编号小的优先。因此可以给每个医生建立一个优先队列来维护排队的人。之后，只要注意所有队列时间同步的问题，让每个检查的人，插到下一个检查项目的队列中，模拟到所有人都检查完即可。