题目概述
假设有N个客户在K个窗口等待服务。 每个窗口可以容纳一个人, 因此其他客户需要进行等待. 当某个客户服务完成后, 下一个客户可以进入该窗口并被服务. 我们假设没有窗口会被占用1小时以上.
现在我们给出每个客户的到达时间T和服务该客户所需要的时间P, 请计算所有客户的平均等待时间.
输入
每个输入文件包含一个测试用例. 每个测试用例, 第一行包含两个整数N( <= 1000)和K( <= 100). 其中N表示客户的数量, K表示窗口的数量.
接下来的N行, 包含两个时间: HH:MM:SS, 表示客户的到达时间; P, 表示服务该客户所需要的时间(以分钟为单位).
HH的范围是[00, 23], MM和SS的范围是[00, 59]. 我们假设没有两个客户在同一时间到达.
需要说明的是, 银行的营业时间是08:00-17:00. 如果到达的时间早于08:00, 客户需要等待至银行开始营业才能被服务; 如果客户晚于(或恰好在)17:00:01到达银行, 则该客户不会被服务, 因此也无需计算该客户的平均等待时间.
输出
对于每一个测试用例, 请输出客户的平均等待时间, 以分钟为单位, 并精确到一位小数.
解题思路
典型的模拟题, 并且比PAT 1014要简单一点的模拟题.
读入数据时, 自动过滤17:00:00以后到达的客户.
按客户先后到达顺序进行服务, 在客户服务完成后, 更新窗口的服务完成时间.
客户每次选择服务完成时间最短的进行排队(服务).
需要考虑如下情况:
- 若银行未营业, 则客户需要等待;
(以及在“遇到的问题”中阐述的一些情况)
遇到的问题
若干次WA, 存在如下需要考虑的情况
1. 若所有顾客都在17:00:00以后到达, 则结果为0.0;
2. 若当前所有顾客都已服务完毕, 但是下一位顾客还未到来, 需要窗口需要等待;
3. 若当前客户不需要等待, 则该窗口服务完成时间时为客户到达时间 + 服务时间; 否则, 该窗口服务完成时间为上一个客户完成的时间 + 该客户服务时间.