PAT甲级 1014 排队等候（队列大模拟+格式化时间）

原题链接

假设一家银行有 N 个服务窗口。

窗户前面有一条黄线，将等候区分为两部分。

客户排队等候的规则是：

在黄线以内的区域，每个窗口前都可以排一队人，每队最多可以排 M 个人，当 N 个窗口前的队伍都排满时，第 NM+1 个顾客以及以后的顾客只能在黄线以外的区域等候。黄线外的所有客户统一排成一个长队。
每当客户进入黄线以内时，他会选择到当前排队人数最少的窗口处排队等待办理业务。当多个窗口前排队人数最少时，客户会选择窗口编号更小的窗口处排队等待办理业务。
第 i 名客户的办理业务时长为 Ti。
最开始的 N 名客户将于早上 08:00 被受理业务。
现在，给定所有客户办理业务所需的时间，并对你进行若干次询问，每次询问一名客户办理完自身业务时的确切时间。

例如，假设银行共有 2 个服务窗口，每个窗口内可以有两名客户排在黄线以内。

现在共有 5 名客户等待办理业务，他们的业务时长分别为 1,2,6,4,3 分钟。

早上 08:00 时，客户 1 在窗口 1 接受服务，客户 2 在窗口 2 接受服务，客户 3 在窗口 1 前等待，客户 4 在窗口 2 前等待，客户 5 在黄线以外等待。

在 08:01，客户 1 办完业务，客户 5 进入黄线以内，并于窗口 1 前等待。

客户 2 将于 08:02 办完业务，客户 4 将于 08:06 办完业务，客户 3 将于 08:07 办完业务，客户 5 将于 08:10 办完业务。

输入格式
第一行包含 4 个整数，N,M,K,Q，分别表示窗口总数，黄线内每个队伍的最大长度，客户总数，询问次数。

第二行包含 K 个整数，表示每个客户办理业务的所需时长（单位：分钟）。

第三行包含 Q 个整数，表示询问的所有客户的编号。

客户编号从 1 到 K。

输出格式
对于每个询问的客户，输出其办理完业务的确切时间，格式为 HH:MM。

注意，银行 17:00 就会停止受理新的业务，所以对于不能在 17:00 之前（即最晚可以开始服务的时间是16:59）开始办理业务的客户，要输出 Sorry。

数据范围
1≤N≤20,
1≤M≤10,
1≤K≤1000,
1≤Q≤K
输入样例：
2 2 7 5
1 2 6 4 3 534 2
3 4 5 6 7
输出样例：
08:07
08:06
08:10
17:00
Sorry

我的解法：

#include <bits/stdc++.h>
using namespace std;

const int N = 40;

queue <int> q[N];
int n, m, k, Q;
int sum[N];

int main(){
    cin >> n >> m >> k >> Q;
    
    unordered_map<int, int> hash;
    
    for(int i = 1; i <= k; i ++ ){
        int x;
        cin >> x;
        int t = 0;
        for(int j = 0; j < n; j ++ ){
            if(i <= n * m){
                if(q[j].size() < q[t].size()) t = j;
            } 
            else{
                if(q[j].front() < q[t].front()) t = j;
            }
        }
        sum[t] += x;
        if(i > n * m) q[t].pop();
        q[t].push(sum[t]);
        
        if(sum[t] - x < 540) hash[i] = sum[t];
    }
    
    while(Q -- ){
        int i;
        cin >> i;
        if(hash.count(i)) printf("%02d:%02d\n", hash[i]/60 + 8, hash[i]%60);
        else puts("Sorry");
    }
    
    return 0;
}

收获：

队列数组模拟排队流程+hash表快速查找结果

格式化打印时间 printf("%02d:%02d\n", hash[i]/60 + 8, hash[i]%60);