题目
题目链接：1017 Queueing at Bank （PAT (Advanced Level) Practice）
输入样例
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输出样例
8.2提交结果截图
带详细注释的源代码
#include <iostream>
#include <queue>
#include <algorithm>
#include <cstdio>
using namespace std;
#define open_time 8*3600//开门时间
#define close_time 17*3600//关门时间
struct Customer
{
int arrive_time;//到达时间
int process_time;//服务时间
int leave_time;//离开时间
}customer[10001];
bool cmp(Customer a, Customer b)
{
return a.arrive_time < b.arrive_time;
}
int N,K;//N->客户人数，K->窗口数量
float wait_time = 0;//总等待时间
int serve_num;//总服务人数（关门了才来的人不服务，也就没必要算入平均）
int main()
{
cin>>N>>K;
serve_num = N;//初始为N
int h, m, s, t;
queue<Customer>Windows[101];
for(int i = 0; i < N; i++)
{
scanf("%d:%d:%d", &h, &m, &s);
t = 3600*h + 60*m + s;//将到达时间转化成秒
customer[i].arrive_time = t;
cin>>customer[i].process_time;
customer[i].process_time*=60;//将服务时间（分钟）转换位秒
}
sort(customer, customer+N, cmp);//排序
for(int i = 0; i < N; i++)
{
int per_wait_time = 0, window = 0;
if(customer[i].arrive_time < open_time)//来早了
per_wait_time += open_time - customer[i].arrive_time;
else if(customer[i].arrive_time > close_time)//来晚了
{
serve_num--;
continue;
}
for(int j = 0; j < K; j++)//查看窗口状态
{
if(Windows[j].empty())//如果窗口队列位空
{ //计算客户离开时间（其中服务开始必须等到开门才行）
customer[i].leave_time = max(customer[i].arrive_time, open_time) + customer[i].process_time;
Windows[j].push(customer[i]);//入队
window = -1;//作标记
break;
}
else if(Windows[window].back().leave_time > Windows[j].back().leave_time)//寻找最快可以服务的窗口
window = j;
}
if(window != -1)
{
Customer previous_customer = Windows[window].back();//排在该窗口的上一个人
if(customer[i].arrive_time - previous_customer.leave_time < 0)//说明要排队
{ //计算等待时间和离开时间
per_wait_time += previous_customer.leave_time - customer[i].arrive_time;
customer[i].leave_time = previous_customer.leave_time + customer[i].process_time;
}
else//不用排队说明不用等待
customer[i].leave_time = customer[i].arrive_time + customer[i].process_time;
Windows[window].push(customer[i]);//入队
}
wait_time += per_wait_time;//单人服务时间累加到总服务时间中
}
printf("%.1f", wait_time/60/serve_num);
return 0;
}