# PAT 1017 Queueing at Bank (25分) prioriry_queue

### 题目

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

### 思路分析

• 首先用结构体保存所有客户的到达时间和办理业务需要的时间，因为客户到达时间是以`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()，这个类就有了类似函数的行为，就是一个仿函数类了）```
• 所以，对于每个用户，==判断堆顶元素是不是比自己的到达时间早==，如果是，说明在在自己来之前这个窗口就可以结束服务，然后我就可以直接过去，相当于我不用等待，这个时候我们只需要==弹出堆顶元素（相当于这个窗口在我来之前结束当前服务），压入新的元素（我过来后这个窗口当前服务结束时间就改变了）==；如果堆顶元素比我到达的时间还大呢？那我就要等待了，等那个窗口服务完再去排队，这是我们就要统计等待时间，之后的操作类似，还是弹出堆顶元素（相当于这个窗口在我来之前结束当前服务），压入新的元素（我过来后这个窗口当前服务结束时间就改变了）；
• 注意我们为什么只需要判断堆顶元素呢？因为我们用的是最小堆，堆顶元素就是k个窗口中最早结束当前服务的那个窗口的结束时间，而顾客每次选择就是按照哪个窗口先结束就去哪个窗口排队的原则进行选择。

### 满分代码

```#include <algorithm>
#include <iostream>
#include <queue>
using namespace std;

struct People {
// 全部以秒为单位进行记录
int arrive_time, process_time;
} people[10000];

// 用于升序排序
bool cmp(People c1, People c2) {return c1.arrive_time < c2.arrive_time;}

int main() {
// 银行开始服务时间，结束服务时间
int bank_open_time = 8 * 3600, bank_close_time = 17 * 3600;
// n 个人，k 个窗口
int n, k;
cin >> n >> k;
// 记录有效的，被服务的客户数目
int index = 0;
// 所有被服务的客户的等待时间
int total_wait_time = 0;
int h, m, s, p;
for (int i = 0; i < n; ++i) {
scanf("%d:%d:%d %d", &h, &m, &s, &p);
int time = h * 3600 + m * 60 + s;
// 在 17:00之后到达，不会被服务，不用记录，不用于计算平均时间
if (time > bank_close_time) continue;
// 保存这个客户记录，index+=1
people[index].arrive_time = time;
if (p > 60) p = 60; // 每个窗口服务不会超过1小时，相当于把他的占用时间改为1小时
people[index].process_time = p * 60;
index++;
}
// 根据到达时间进行排序
sort(people, people + index, cmp);
// 用一个优先队列维护k个窗口当前服务结束时间，使用小顶堆
// 第二个参数必须是用数组实现的容器，比如vector,deque等等，但不能用 list。STL里面默认用的是vector
// greater和less是std实现的两个仿函数（就是使一个类的使用看上去像一个函数。其实现就是类中实现一个operator()，这个类就有了类似函数的行为，就是一个仿函数类了）
// 默认实现的是大顶堆
priority_queue<int, vector<int>, greater<int>> minheap;
// 首先k个窗口都是8:00开始服务，相当于它当前服务的结束时间都是8:00
while (k-- > 0)
minheap.push(bank_open_time);
// 顾客已经排好序了，逐个处理
for (int i = 0; i < index; ++i) {
// 最早结束服务的那个窗口服务在他来之前能够结束服务，甚至可能已经空了一会
if (minheap.top() <= people[i].arrive_time) {
// 不用等待
// pop()相当于那个窗口结束上一个服务
// 接着窗口为他服务，那么这个窗口这次的结束时间就是 【这个人来的时间+这个人需要的时间】
minheap.push(people[i].arrive_time + people[i].process_time);
// 本应该先结束服务再为他服务，但先pop()栈顶元素改变，我们得先保存top()
minheap.pop();
} else {
// 他需要等 最早的那个窗口结束当前服务
total_wait_time += minheap.top() - people[i].arrive_time;
// 然后窗口结束服务，为他服务，最小堆pop()并插入新元素
// 这里与上面的区别的是，窗口这次的结束时间是 【窗口上次的结束时间+这个人的等待时间】
minheap.push(minheap.top() + people[i].process_time);
// 本应该先结束服务再为他服务，但先pop()栈顶元素改变，我们得先保存top()
minheap.pop();
}
}
// 以分钟输出平均等待时间
printf("%.1f", total_wait_time / 60.0 / index);

return 0;
}```

0 条评论

• ### PAT 1044 Shopping in Mars (25分) 二分法

Shopping in Mars is quite a different experience. The Mars people pay by chained...

At the beginning of every day, the first person who signs in the computer room w...

• ### PAT 1005 Spell It Right (20分)

Given a non-negative integer N, your task is to compute the sum of all the digit...

• ### leetcode 5 Longest Palindromic Substring--最长回文字符串

Given a string S, find the longest palindromic substring in S. You may assume th...

• ### PAT 1004

A family hierarchy is usually presented by a pedigree tree. Your job is to count...

• ### 杭电 1789（贪心思维练习）

Ignatius has just come back school from the 30th ACM/ICPC. Now he has a lot of h...

• ### LWC 58：724. Find Pivot Index

LWC 58：724. Find Pivot Index 传送门：724. Find Pivot Index Problem: Given an array ...

• ### 2488 绿豆蛙的归宿

2488 绿豆蛙的归宿 时间限制: 1 s 空间限制: 64000 KB 题目等级 : 黄金 Gold 题目描述 Description 　　随着...

• ### POJ 1985 Cow Marathon(树的直径)

Description After hearing about the epidemic of obesity in the USA, Farmer John...

• ### Ants（POJ No.1852）

该题目的关键点在于当两个蚂蚁相遇时，各自往回走的情况等价于两只蚂蚁按原来的方向继续走。类似于小球的弹性碰撞。