题目描述

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

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

客户排队等候的规则是：

在黄线以内的区域，每个窗口前都可以排一队人，每队最多可以排 M 个人，当 N 个窗口前的队伍都排满时，第 NM+1 个顾客以及以后的顾客只能在黄线以外的区域等候。黄线外的所有客户统一排成一个长队。
每当客户进入黄线以内时，他会选择到当前排队人数最少的窗口处排队等待办理业务。当多个窗口前排队人数最少时，客户会选择窗口编号更小的窗口处排队等待办理业务。
第$ i$ 名客户的办理业务时长为 $T_i$。
最开始的 $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 之间开始办理业务的客户，要输出 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

算法

模拟 $O(K*N)$

模拟排队
用分钟来做时间轴, 窗口的开始时间设定为 480， 也就是早上8:00
一个顾客类: 成员变量id唯一标识每个顾客, time 表示顾客需要办理业务的时间,
一个窗口类: 成员变量startTime 表示该窗口当前办理顾客的开始时间,queue<Cus>表示当前窗口中的顾客

1. 读取所有数据
   将顾客id和time存入custom队列中
   将查询的顾客存入qlist中
2. 窗口初始化填充
   需要先将窗口填充完，然后再模拟服务过程
   按照窗口id从小到大开始填充
   只要最后一个窗口的顾客数小于M就一直填充
3. 一边服务一边将黄线以外的顾客放入黄线内
4. 黄线外以及没有顾客了，将黄线内的顾客全部服务
5. 根据qlist进行查询

时间复杂度 $O(K*N) $

读取数据 $O(K)$

顾客服务 $O(K)$ , 服务的时候要查询最早出现的窗口 $O(N)$, 所以总共 $O(N*K)$

查询 $O(Q)$

由数据范围可知最坏的情况下 K最大，所以时间复杂度是 $O(K*N)$

注意事项

只要服务的开始时间在 8:00 到 17.00 之间就可以被服务，和服务结束时间无关

也就是说在16:59开始服务，20:00结束服务也是符合要求的

输出的Sorry 第一个字母要大写

C++ 代码

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

class Cus {
public:
    Cus(int a,int b) {
        id = a;
        time = b;
    }
    int id = 0;
    int time = 0;
};
class Win {
public:
    int startTime = 480;
    queue<Cus> q;
};

int main() {
    int n, m, k, q;
    cin >> n >> m >> k >> q;
    vector<int> times(k + 1, 0), qlist(q, 0);
    vector<Win> windows(n);
    queue<Cus> customs;
    vector<int> res(k+1,0);
    for (int i = 1; i < k + 1; i++) {
        int time;
        scanf("%d", &time);
        Cus cus(i,time);
        customs.push(cus);
    }
    for (int i = 0; i < q; i++) cin >> qlist[i];

    //填充窗口
    int win_idx = 0;
    while (windows.back().q.size() < m && !customs.empty()) {
        windows[win_idx].q.push(customs.front());
        customs.pop();
        win_idx = (win_idx + 1) % n;
    }
    //模拟整个过程
    while (!customs.empty()) {
        //黄线以外的第一个顾客
        Cus waiting_cus = customs.front();
        customs.pop();
        int min_time = INT_MAX;
        int win_idx = 0;

        //寻找最早出现空位的窗口
        for (int i = 0; i < n; i++) {
            int cur_time = windows[i].q.front().time + windows[i].startTime;
            if (cur_time < min_time) {
                win_idx = i;
                min_time = cur_time;
            }
        }
        //顾客进入窗口排队
        windows[win_idx].q.push(waiting_cus);

        //该窗口的最前面的顾客进行服务
        Cus cur_cus = windows[win_idx].q.front();
        windows[win_idx].q.pop();

        int end_time = windows[win_idx].startTime + cur_cus.time;

        //如果服务开始时间大于 17:00 则该顾客不能得到服务 置 -1
        //否则 结束时间是 窗口的开始时间加上顾客需要的服务时间
        if (windows[win_idx].startTime >= MAX_TIME) {
            cur_cus.time = -1;
        }
        else {
            cur_cus.time = end_time;
        }
        res[cur_cus.id] = cur_cus.time;

        //更新窗口时间
        windows[win_idx].startTime = min(end_time, MAX_TIME);


    }

    //上面操作以及将所有顾客都放入黄线以内，黄线以外以及没有其他顾客了
    //然后对黄线以内的剩余顾客进行服务
    //由于没有其他顾客的干扰，只需要按照窗口顺序，以此将所有队列中的顾客服务完毕即可
    for (int i = 0; i < n; i++) {
        while (!windows[i].q.empty()) {
            Cus cur_cus = windows[i].q.front();
            windows[i].q.pop();

            int end_time = windows[i].startTime + cur_cus.time;
            if (windows[i].startTime >= MAX_TIME) {
                cur_cus.time = -1;
            }
            else {
                cur_cus.time = end_time;
            }
            res[cur_cus.id] = cur_cus.time;
            windows[i].startTime = min(MAX_TIME, end_time);
        }
    }

    //按照qlist 的顺序输出
    for (auto& t : qlist) {
        int time = res[t];
        if (time == -1) {
            printf("Sorry\n");
        }
        else {
            int h = time / 60;
            int m = time % 60;
            printf("%02d:%02d\n", h, m);
        }
    }
    return 0;
}