【PAT甲级】1017 Queueing at Bank

✍个人博客：https://blog.csdn.net/Newin2020?spm=1011.2415.3001.5343
📚专栏地址：PAT题解集合
📝原题地址：题目详情 - 1017 Queueing at Bank (pintia.cn)
🔑中文翻译：银行排队
📣专栏定位：为想考甲级PAT的小伙伴整理常考算法题解，祝大家都能取得满分！
❤️如果有收获的话，欢迎点赞👍收藏📁，您的支持就是我创作的最大动力💪

1017 Queueing at Bank

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 (≤104) - 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
1
2
3
4
5
6
7
8

Sample Output:

8.2
1

思路

1. 先用结构体数组 $persons$ 将所有客户到达以及服务时间记录起来，为了方便后续判断，我们统一将给定的时间转换成秒来存储。
2. 初始化所有窗口，用小根堆来维护所有窗口的开始时间。我们可以直接用 $STL$ 中的优先队列 $priority\_queue$ ，其 $top$ 元素就是最小值。注意，由于银行是 $8$ 点上班，所以初始化时存进去的秒是 $8\ast 3600$ 。
3. 对结构体数组 $persons$ 进行排序，以客户的到达时间为标准从小到大进行排序。
4. 遍历排完序的结构体数组，每次遍历都从小根堆中寻找一个开始时间最早的窗口，然后更新等待时间。如果当前客户的到达时间已经大于下班时间，则直接 $break$ 。注意，如果只要客户到达时间在 $17$ 点之前，那么即使过了 $17$ 点也能被服务。
5. 输出平均等待时间，注意这里输出的是分钟，而我们记录的是秒数，所以求完平均后还要除以 $60$ 转换成分钟输出。

代码

#include
using namespace std;

const int N = 10010;
int n, m;
struct person {
    int arrive_time;
    int service_time;
    bool operator <(const person& p)const
    {
        return arrive_time < p.arrive_time;
    }
}persons[N];

//小根堆，快速找到下一个最早能用的窗口
priority_queue<int, vector<int>, greater<int>> windows;

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 }; 
    }

    for (int i = 0; i < m; i++)    windows.push(8 * 3600);

    sort(persons, persons + n);

    int sum = 0, cnt = 0;
    for (int i = 0; i < n; i++)
    {
        auto person = persons[i];
        auto w = windows.top();
        windows.pop();
        if (person.arrive_time > 17 * 3600)   break;  //如果来晚了，后面的人都忽略
        int start_time = max(w, person.arrive_time); //该窗口最早开始时间  
        sum += start_time - person.arrive_time; //更新等待时间
        cnt++;
        windows.push(start_time + person.service_time);
    }

    printf("%.1f\n", (double)sum / cnt / 60);

    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49