pat 甲级 1017 Queueing at Bank

这道题模拟题，有部分思想跟1016题的电话账单相类似。

1.该如何存储每个人的到达时间并进行比较。可以将每个人的到达时间转换成距离00：00：00的秒数。统一标准，方便比较，例如当time>17*60*60（17：00：00） 表示来得太晚都将不被服务；同时因为还要保存服务时间，可以考虑将到达时间与服务时间用结构体存储。存储服务时间的时候，若大于一小时，则终止服务（题目要求），故存储的服务时间为min（服务时间，60*60）；

struct Person
{
    int arrive_time;
    int service_time;
}persons[N];

2.多个窗口，要去时间最小的窗口进行服务(等待时间最短）。故可以考虑使用小根堆来维护窗口(堆顶就是最小值），无须我们手动维护；注意因为每个人的到达时间转换成距离00：00：00的秒数，窗口的开放时间为08：00：00,故小根堆需要初始化为8*60*60；选择时间最小的窗口进行服务后，要对窗口的值进行更新，开始服务时间+min(服务时间，60*60）。同时若到达时间小于窗口的最小值，说明需要等待，要记录等待时间（开始服务时间-到达时间）；

代码如下：

#include<iostream>
#include<queue>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<vector>

using namespace std;

const int N = 10010, M = 110;//+10防止越界
int n, m;
struct Person
{
    int arrive_time;
    int service_time;
    bool operator< (const Person& a) const// 在结构体里重载运算符，按照到达时间进行从小到大排序
    {
        return arrive_time < a.arrive_time;
    }
}persons[N];
int main()
{
    cin >> n >> m;
    for (int i = 0; i < n; i ++ )
    {
        int hour, minute, second,service_time;
        scanf("%d:%d:%d %d", &hour, &minute, &second, &service_time);
        service_time = min(service_time, 60);//服务时间超过一小时，终止服务，故最大值只能是60min
        persons[i] = {hour * 3600 + minute * 60 + second, service_time * 60}; //保存秒数
    }
    priority_queue<int, vector<int>, greater<int>> windows;  //定义小根堆
    for (int i = 0; i < m; i ++ ) windows.push(8 * 3600);  // 初始化窗口，从08:00:00开始
    sort(persons, persons + n);
    int wait_time = 0, cnt = 0;
    for (int i = 0; i < n; i ++ ) 
    {
        auto person = persons[i];
        if (person.arrive_time > 17 * 3600) break;//17：00：00后来的，不被服务
        int w = windows.top();  // 窗口最小值
        windows.pop();  // 用了窗口最小值就把他删掉，之后更新后再插入小根堆
        if(person.arrive_time <w)//小于窗口最小值，需要等待
               wait_time+=w-person.arrive_time ;
        cnt ++;
        windows.push( max(person.arrive_time, w) + person.service_time);
    }
    printf("%.1lf\n", (double)wait_time / cnt / 60);//平均等待分钟数
    return 0;
}