【PAT甲级】1017 Queueing at Bank

简介: 【PAT甲级】1017 Queueing at Bank

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


Sample Output:

8.2

思路

先用结构体数组 p e r s o n s personspersons 将所有客户到达以及服务时间记录起来,为了方便后续判断,我们统一将给定的时间转换成秒来存储。

初始化所有窗口,用小根堆来维护所有窗口的开始时间。我们可以直接用 S T L STLSTL 中的优先队列 p r i o r i t y _ q u e u e priority\_queuepriority_queue ,其 t o p toptop 元素就是最小值。注意,由于银行是 8 88 点上班,所以初始化时存进去的秒是 8 ∗ 3600 8*36008∗3600 。

对结构体数组 p e r s o n s personspersons 进行排序,以客户的到达时间为标准从小到大进行排序。

遍历排完序的结构体数组,每次遍历都从小根堆中寻找一个开始时间最早的窗口,然后更新等待时间。如果当前客户的到达时间已经大于下班时间,则直接 b r e a k breakbreak 。注意,如果只要客户到达时间在 17 1717 点之前,那么即使过了 17 1717 点也能被服务。

输出平均等待时间,注意这里输出的是分钟,而我们记录的是秒数,所以求完平均后还要除以 60 6060 转换成分钟输出。

代码

#include<bits/stdc++.h>
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;
}


目录
相关文章
|
5月前
|
机器学习/深度学习 定位技术 数据格式
【数据分享】银行客户流失Bank Customer Churn数据
【数据分享】银行客户流失Bank Customer Churn数据
|
5月前
|
人工智能
【2024美赛】F题(中英文):减少非法野生动物贸易Problem F: Reducing Illegal Wildlife Trade
【2024美赛】F题(中英文):减少非法野生动物贸易Problem F: Reducing Illegal Wildlife Trade
54 0
|
5月前
GE Fanuc通用电气 IC670CHS003 I/O端子板
GE Fanuc通用电气 IC670CHS003 I/O端子板
GE Fanuc通用电气  IC670CHS003 I/O端子板
|
5月前
|
编解码
GE Fanuc通用电气 IC660BBA100 模拟输入/输出模块
GE Fanuc通用电气 IC660BBA100 模拟输入/输出模块
|
5月前
|
JSON 算法 API
金润数科JR-CLT-002-通过型号查询车型信息
接口名称 通过型号查询车型信息 接口编号 JR-CLT-002 接口描述 通过型号查询车型信息 接口地址 /dmp/api 请求方式 POST 加密方式 RSA2
|
C++
【PAT甲级 - C++题解】1037 Magic Coupon
【PAT甲级 - C++题解】1037 Magic Coupon
69 1
【PAT甲级】1146 Topological Order
【PAT甲级】1146 Topological Order
58 0
|
算法框架/工具
【PAT甲级】1126 Eulerian Path
【PAT甲级】1126 Eulerian Path
58 0
|
存储
【PAT甲级】1139 First Contact
【PAT甲级】1139 First Contact
73 0
|
存储
【PAT甲级】1122 Hamiltonian Cycle
【PAT甲级】1122 Hamiltonian Cycle
49 0