PAT1017Queueing at Bank&1014Waiting in Line

想把两个背景相似的题做一个总结,都是银行窗口排队办业务之类的~

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 (≤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:

1
2
3
4
5
6
7
8
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:

1
8.2

题目大意:
N个客户,K个窗口。给出每个客户到达的时间和服务时长,若所有窗口都被占用那么客户在黄线外排队。求客户平均等待时长。银行开放时间8:00-17:00,8点之前到达的需等待,17点之后还未被服务的客户不算在内,超过一小时的缩减为一小时。
思路:
用结构体node存放每个客户到达时间和服务时长,读入所有数据后将17:00前到达的客户按到达时间排序。window数组存放每个窗口当前客户的服务结束时间,找到最早空闲的窗口让下一客户前往该窗口,同时更新窗口服务结束时间。如果客户到达时间比最早空闲的窗口时间晚,则等待时间为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
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
struct node{
int T,P;
};
int n,k;
vector<node> customer;
bool cmp(node a,node b){
return a.T<b.T;
}
int main(){
int hh,mm,ss,pp;
scanf("%d%d",&n,&k);
for(int i=0;i<n;i++){
scanf("%d:%d:%d %d",&hh,&mm,&ss,&pp);
int T=3600*hh+60*mm+ss-28800; //把8点设为0点
if(T>32400) continue; //(17-8)*60*60
if(pp>60) pp=60; //超过1h的时长会被缩短为1h(不过测试点中好像没有这种情况)
customer.push_back(node{T,pp*60});
}
sort(customer.begin(),customer.end(),cmp);
vector<int> window(k,0);
double ans=0.0;
for(int i=0;i<customer.size();i++){
int tindex=0,min=window[0];
for(int j=1;j<k;j++){
if(window[j]<min){
tindex=j;
min=window[j];
}
}
if(window[tindex]<=customer[i].T)
window[tindex]=customer[i].T+customer[i].P;
else{
ans+=(window[tindex]-customer[i].T);
window[tindex]+=customer[i].P;
}
}
if(customer.size()==0) printf("0.0");
else printf("%.1f",ans / 60.0 / customer.size());
return 0;
}

1014 Waiting in Line

Suppose a bank has N windows open for service. There is a yellow line in front of the windows which devides the waiting area into two parts. The rules for the customers to wait in line are:
·The space inside the yellow line in front of each window is enough to contain a line with M customers. Hence when all the N lines are full, all the customers after (and including) the (NM+1)st one will have to wait in a line behind the yellow line.
·Each customer will choose the shortest line to wait in when crossing the yellow line. If there are two or more lines with the same length, the customer will always choose the window with the smallest number.
·Customer i​​ will take T​i​​ minutes to have his/her transaction processed.
·The first N customers are assumed to be served at 8:00am.
Now given the processing time of each customer, you are supposed to tell the exact time at which a customer has his/her business done.
For example, suppose that a bank has 2 windows and each window may have 2 custmers waiting inside the yellow line. There are 5 customers waiting with transactions taking 1, 2, 6, 4 and 3 minutes, respectively. At 08:00 in the morning, customer​1​​ is served at window​1​​ while customer​2​​ is served at window​2​​. Customer​3​​ will wait in front of window​1​​ and customer​4​​ will wait in front of window
​2​​. Customer​5​​ will wait behind the yellow line.
At 08:01, customer​1​​ is done and customer​5​​ enters the line in front of window​1​​ since that line seems shorter now. Customer​2​​ will leave at 08:02, customer​4​​ at 08:06, customer​3​​ at 08:07, and finally customer​5​​ at 08:10.

Input Specification:

Each input file contains one test case. Each case starts with a line containing 4 positive integers: N (≤20, number of windows), M (≤10, the maximum capacity of each line inside the yellow line), K (≤1000, number of customers), and Q (≤1000, number of customer queries).
The next line contains K positive integers, which are the processing time of the K customers.
The last line contains Q positive integers, which represent the customers who are asking about the time they can have their transactions done. The customers are numbered from 1 to K.

Output Specification:

For each of the Q customers, print in one line the time at which his/her transaction is finished, in the format HH:MM where HH is in [08, 17] and MM is in [00, 59]. Note that since the bank is closed everyday after 17:00, for those customers who cannot be served before 17:00, you must output Sorry instead.

Sample Input:

1
2
3
2 2 7 5
1 2 6 4 3 534 2
3 4 5 6 7

Sample Output:

1
2
3
4
5
08:07
08:06
08:10
17:00
Sorry

题目大意:
某银行有N个窗口,每个窗口前最多可以排M个人,有K位客户,每位的服务时长已知,假设所有客户均在8:00按客户编号次序等在黄线外,如果有窗口排队人数没有满M人,站在黄线外的第一个客户就会选择这个窗口的队伍,Q个查询,每个查询给出一位客户编号,输出这位客户服务结束时间,如果17:00(包括17:00)以后该客户还未被服务,则Sorry,如果17点前以开始服务,不管多晚都服务结束。
注意事项:
这里选择窗口的依据不是窗口的最早空闲时间,而是该窗口黄线以内的人数最少优先,不管前面这个人的服务时间有多长(毕竟我们去排队是不知道前面这个人要折腾多久的),只会优先选择最短的那个队伍。解释一下样例,前四个人就不说了,从5号开始,1窗口第一个人1分钟就结束了,队伍比2窗口先变短,于是3号去了1窗口,同理6号去了2窗口,7号就比较惨,因为此时2窗口的队首4分钟结束了,比1窗口那个6分钟的快,于是她去了2窗口,然而前面是6号这个磨叽的客户,最后服务完6号银行关门了于是7号就sorry了…
思路:
开N个队列记录当前该窗口队伍中的客户编号,以便后续客户选择队伍时查询队首客户的结束时间,选择队首客户结束时间最早的,然后将队首出队,当前客户入队,并更新该客户结束服务时间。

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
#include<cstdio>
#include<vector>
#include<queue>
using namespace std;
struct node{
int pt,time;
};
int main(){
int n,m,k,q,temp;
scanf("%d%d%d%d",&n,&m,&k,&q);
vector<node> cus(k);
vector<int> win(n,0);
queue<int> que[n];
for(int i=0;i<k;i++){
scanf("%d",&cus[i].pt);
}
for(int i=0;i<k;i++){
int min=0;
for(int j=0;j<n;j++){
if(que[j].size()<que[min].size())
min=j;
}
if(que[min].size()==m){
for(int j=0;j<n;j++){
if(cus[que[j].front()].time<cus[que[min].front()].time)
min=j;
}
que[min].pop();
}
que[min].push(i);
cus[i].time=win[min]>=540?-1:win[min]+cus[i].pt;
win[min]+=cus[i].pt;
}
for(int i=0;i<q;i++){
scanf("%d",&temp);
temp--;
if(cus[temp].time==-1){
printf("Sorry\n");
continue;
}
int ti=cus[temp].time+8*60;
printf("%02d:%02d\n",ti/60,ti%60);
}
return 0;
}