【PAT】PAT A1014 Waiting in Line【快乐模拟】
Assume a bank has N service windows open. A yellow demarcation line positioned in front of these windows segregates the waiting area into two defined zones. The regulations governing customer queue management are:
位于每扇窗前黄线内的空间足以容纳包含M名客户的队列。因此当所有N条队列都已满员时，在黄线之后的（NM+1）号及之后的所有顾客将不得不排在黄线后的队列中等待。
每位顾客在越过黄线时都会选择最短的队列等待。
第i位顾客将花费Ti分钟完成其交易。
前N位顾客被假设于8:00am开始服务。
现在，请根据每位顾客的处理时间来确定某位顾客在其业务完成的具体时间。
For instance, consider a bank with two teller windows; each window might accommodate two customers waiting within the yellow line. There are five customers awaiting service with transaction durations of one, two, six, four, and three minutes respectively. At eight o'clock in the morning, customer one will be attended by teller one while customer two will be handled by teller two. Customer three will stand by teller one's counter and customer four will stand by teller two's counter. Customer five will be positioned behind the yellow line waiting for their turn.
At 08:01, customer1 is done and customer5 enters the line in front of window1 since that line seems shorter now. Customer2 will leave at 08:02, customer4 at 08:06, customer3 at 08:07, and finally customer5 at 08:10.
Input Specification:
Each input file encompasses a single test case. Each instance begins with a line that includes four key numerical values: window count (≤ 20), max capacity per yellow zone line (≤ 10), customer count (≤ 1,000), and customer query count (≤ 1,000).
The next line includes K positive integers, which represent the processing times of each of the K customers.
This section includes Q positive integers, which denote customer inquiries regarding the time required for each transaction. These integers indicate Customer inquiries, and they are assigned numbers ranging from 1 to K.
Output Specification:
For each of the Q customers, output a single line containing their transaction completion time in the format HH:MM where HH ranges from 08 to 17 and MM ranges from 00 to 59. Note that since the bank operates only until 17:00 each day, any transactions not completed by that time should result in outputting 'Sorry' instead.
Sample Input:
2 2 7 5
1 2 6 4 3 534 2
3 4 5 6 7
Sample Output:
08:07
08:06
08:10
17:00
Sorry
题目大意
共有N个服务窗口，在每个window前面都有黄线标识，并规定每个window前面最多可容纳M位等待客户。当顾客到达银行时，默认会优先选择人少的那个window进入排队，并且如果在同一时间有多个window的人数相同，则优先选择具有较小编号的那个window进行排队。特别地，在下午五点之前还未接受过服务并且尚未完成相关业务流程的一位顾客，则无法继续办理该业务。若需查询某位正在排队并等待接受服务的朋友，请告知他的名字以及他所在的queue号码；如果朋友已经超过了截止时间仍未被成功接通，请返回提示信息'抱歉'
代码
#include <iostream>
#include <cstdio>
#include <queue>
#include <vector>
#include <algorithm>
using namespace std;
#define maxK 1001
#define maxN 20
#define maxM 10
struct Window{
queue<int> q;
int popTime;
}windows[maxN];
int cost[maxK];
int finished[maxK];
int n, m, k, q;
// 填满黄线前的位置
int fillWindow(){
int id = 1;
for(int j = 0; j < n; j++){
windows[j].popTime = cost[id];
windows[j].q.push(id);
if(++id > k) return id;
}
for(int i = 0; i < m - 1; i++){
for(int j = 0; j < n; j++){
windows[j].q.push(id);
if(++id > k) return id;
}
}
return id;
}
int main() {
scanf("%d %d %d %d", &n, &m, &k, &q);
for(int i = 1; i <= k; i++){
scanf("%d", &cost[i]);
}
// 初始化完成时间， -1代表无法完成业务
fill(finished, finished + maxK, -1);
int id = fillWindow();
// 模拟
for(int t = 0; t < 540; t++){
for(int i = 0; i < n; i++){
if(windows[i].popTime != t) continue;
// 出列， 记录完成时间
finished[windows[i].q.front()] = t;
windows[i].q.pop();
if(windows[i].q.size() > 0){
// 更新出列时间
windows[i].popTime = t + cost[windows[i].q.front()];
}
if(id > k) continue;
// 空出空位， 黄线外的客户进去一个
windows[i].q.push(id);
id++;
}
}
// 完成每个窗口当前服务的客户（如果有的话）
for(int i = 0; i < n; i++){
if(windows[i].q.size() < 1) continue;
finished[windows[i].q.front()] = windows[i].popTime;
}
int query, timestamp;
for(int i = 0; i < q; i++){
scanf("%d", &query);
timestamp = finished[query];
if(timestamp == -1){
printf("Sorry\n");
continue;
}
printf("%02d:%02d\n", timestamp / 60 + 8, timestamp % 60);
}
return 0;
}