已知客户的到达时间T和服务该客户所需时间计算所有客户的平均等待时间

已知客户的到达时间T和服务该客户所需时间计算所有客户的平均等待时间2015-02-11

题目概述

假设有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. 若当前客户不需要等待, 则该窗口服务完成时间时为客户到达时间 + 服务时间; 否则, 该窗口服务完成时间为上一个客户完成的时间 + 该客户服务时间.