Suppose a bank has K windows open for service. There is a yellow line in front of the windows which devides the waiting area into two parts. All the customers have to wait in line behind the yellow line, until it is his/her turn to be served and there is a window available. It is assumed that no window can be occupied by a single customer for more than 1 hour.
Now given the arriving time T and the processing time P of each customer, you are supposed to tell the average waiting time of all the customers.
Input Specification:
Each input file contains one test case. For each case, the first line contains 2 numbers: N (≤10^4) - the total number of customers, and K (≤100) - the number of windows. Then N lines follow, each contains 2 times: HH:MM:SS - the arriving time, and P - the processing time in minutes of a customer. Here HH is in the range [00, 23], MM and SS are both in [00, 59]. It is assumed that no two customers arrives at the same time.
Notice that the bank opens from 08:00 to 17:00. Anyone arrives early will have to wait in line till 08:00, and anyone comes too late (at or after 17:00:01) will not be served nor counted into the average.
Output Specification:
For each test case, print in one line the average waiting time of all the customers, in minutes and accurate up to 1 decimal place.
Sample Input:
7 3
07:55:00 16
17:00:01 2
07:59:59 15
08:01:00 60
08:00:00 30
08:00:02 2
08:03:00 10
Sample Output:
8.2
有n个客户（不超过10000）来银行办理业务，银行有k个窗口（不超过100），银行早上8点开始服务，下午5点结束服务，17:01及以后到达的客户无法被服务；给出这n个客户的到达时间和他们办理业务要花费的时间，最终输出所有客户的平均等待时间，单位为min，精确到小数点后1位。
思路分析这个题目与之前那个 Waiting In Line 的区别在于，所有用户都必须在黄线外等待，然后每当一个窗口结束一个服务，他就过去排队，所以这个题目本身应该是比上个题简单的，但奈何脑子太笨真不怎么想得出来，倒是上个题目自己做出来了。。。奇葩。
首先用结构体保存所有客户的到达时间和办理业务需要的时间，因为客户到达时间是以HH:MM:SS的格式给出的，所以我们全部转化成以秒为单位保存，最后输出的时候再/60.0就可以了。
为了提高效率，我们单独创建一个变量index来记录有效的客户数目，什么叫有效的客户，就是能够被服务的客户，在17:01之前来的客户，所以每次读入一个客户的到达时间时，先判断一下是不是>17:00，如果成立，那我们就不保存他了，这样之后我们处理时效率能高一点。
既然所有用户都要在黄线外等待，那么就好办了，先来后到呗，按到达时间进行排序就可以了。然后就是逐个处理每个客户，就是一个for循环。
对于每个客户，他需要去k个窗口中最早结束当前服务的那个窗口，我们需要记录k个窗口每个窗口当前服务的结束时间，而且还得按结束时间从早到晚排序方便用户去选择，这不很明显了嘛，就是一个最小堆，也就是使用priority_queue。我们在堆里存放每个窗口当前服务的结束时间就可以了。
注：关于这个优先队列，可以看这篇博客，我在这里简单介绍一下
// 定义：priority_queue<Type, Container, Functional> // Type 就是数据类型，Container 就是容器类型 // （Container必须是用数组实现的容器，比如vector,deque等等，但不能用 list。STL里面默认用的是vector）， // Functional 就是比较的方式，当需要用自定义的数据类型时才需要传入这三个参数，使用基本数据类型时，只需要传入数据类型 // 默认是大顶堆 //升序队列 priority_queue <int,vector<int>,greater<int> > q; //降序队列 priority_queue <int,vector<int>,less<int> >q; // greater和less是std实现的两个仿函数（就是使一个类的使用看上去像一个函数。 // 其实现就是类中实现一个operator()，这个类就有了类似函数的行为，就是一个仿函数类了）所以，对于每个用户，判断堆顶元素是不是比自己的到达时间早，如果是，说明在在自己来之前这个窗口就可以结束服务，然后我就可以直接过去，相当于我不用等待，这个时候我们只需要弹出堆顶元素（相当于这个窗口在我来之前结束当前服务），压入新的元素（我过来后这个窗口当前服务结束时间就改变了）；如果堆顶元素比我到达的时间还大呢？那我就要等待了，等那个窗口服务完再去排队，这是我们就要统计等待时间，之后的操作类似，还是弹出堆顶元素（相当于这个窗口在我来之前结束当前服务），压入新的元素（我过来后这个窗口当前服务结束时间就改变了）；