PAT 甲级 1017. Queueing at Bank (25) C++版

Posted on Edited on In

  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

将给出的数据按照时间的先后顺序排列，可以确定为他们服务的次序。 用优先队列去处理，如果队列还可以插入数据（即窗口没满），就直接插入；如果不能插入数据，就弹出优先队列的第一个元素，将要插入的数据与这个弹出来的元素进行比较，可以确定要插入数据等待的时间。 注意：8点前到达的要累加等待的时间，17点后到达的不处理。

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
50
51
52
53
54
55
#include <cstdio>
#include <queue>
#include <algorithm>
#include <vector>
#include <functional>

using namespace std;

struct node {
    int time, p;
};

bool cmp(struct node a, struct node b) {
    return a.time < b.time;
}

int main() {
    int n = 0, k = 0, cnt = 0, waiting = 0;
    scanf("%d %d", &n, &k);
    struct node *arr = new struct node[n];
    for (int i = 0; i < n; i++) {
        int hour = 0, minute = 0, second = 0;
        scanf("%d:%d:%d %d", &hour, &minute, &second, &arr[i].p);
        arr[i].time = hour * 3600 + minute * 60 + second;
        arr[i].p *= 60;
    }
    sort(arr, arr + n, cmp);
    priority_queue<int, vector<int>, greater<int> > q;
    for (int i = 0; i < n; i++) {
        if (arr[i].time > 17 * 3600) {
            break;
        } else {
            cnt++;
            if (q.size() < k) {
                if (arr[i].time < 8 * 3600) {
                    waiting += 8 * 3600 - arr[i].time;
                    arr[i].time = 8 * 3600;
                }
                q.push(arr[i].time + arr[i].p);
            } else {
                int temp = q.top();
                q.pop();
                if (arr[i].time < temp) {
                    waiting += temp - arr[i].time;
                    q.push(temp + arr[i].p);
                } else {
                    q.push(arr[i].time + arr[i].p);
                }
            }
        }
    }
    printf("%.1f", waiting * 1.0 / cnt / 60);
    delete[] arr;
    return 0;
}