pat 甲级 A1039 Course List for Student (25分)

题目链接：

https://pintia.cn/problem-sets/994805342720868352/problems/994805447855292416

题目大意：

某银行开N个窗口办理业务，在每个窗口前设置一条黄线，记最大排队长度为M，现在有K名顾客需要办理业务，有Q名顾客想要查询办理完自己业务的时间，当N个窗口前存在没排满队的情况，下一个在进入黄线时，将选择此时队伍长度最短的进行排队，若最短队伍不止一条，则选择窗口编号最小者；若N个窗口都已经排满，则需要在黄线外等候，待队伍不满时，再进入。由于银行开门时间是8:00到17:00，故若某人开始办理业务时间超过17：00（包括等于17:00），将无法办理业务。

为窗口建立一个结构体window，用endtime记录当前队伍最后服务时间，poptime记录队首客户结束时间，并维护一个该窗口的队列q。

思路分析：

当一位客户进入某一窗口的队列时，他的服务开始时间就确定下来了，即，在该窗前所有人的服务时间之和。

在刚进行排序时，队伍还处于未排满的情况下，当前进入队列的客服将选择队伍人数最少的，且编号最小的队列，即，直接从窗口0~n-1进行排序即可，将当前客户入队，并更新窗口的poptime以及endtime。

当队伍的人数排满时，则需在n个窗口中选择最早有人处理完业务的队伍，poptime最小，且编号最小的队列。

参考代码：

#include <cstdio>
#include <queue>
#include <algorithm>
#include <vector>

using namespace std;
const int maxn = 1010;
int n, m, k, query, q;
int ans[maxn], need[maxn];

int convert(int h, int m){ //将时间单位转换为以分钟，方便时间处理。
    return h*60 + m;
}

struct Pnode{  //窗口当前队伍的最后服务时间，队首客户的服务结束时间
    int endtime, poptime;
    queue <int> q;
};

int main(){
    int pos = 0; //当前第一个未入队编号
    scanf("%d %d %d %d", &n, &m, &k, &query);
    vector <Pnode> window(n);
    for(int i = 0; i < k; i++){  //读入服务时间
        scanf("%d",&need[i]);
    }
    for(int i = 0; i < n; i++){ //初始化每个窗口的endtime以及poptime；
        window[i].endtime = window[i].poptime = convert(8, 0);
    }
    for(int i = 0; i < min(n*m, k); i++){ //当队伍不满时，循环入队
        window[pos%n].q.push(pos);
        window[pos%n].endtime += need[pos];
        if(pos < n) window[pos].poptime = need[pos]; //队伍第一个客户的结束时间
        ans[pos] = window[pos%n].endtime;
        pos++;
    }
    for(; pos < k; pos++){  //若队伍人数过多，一开始入队时，无法全部入队。
        int idx = -1, minpoptime = 1e9;
        for(int i = 0; i < n; i++){  //寻找队伍人数最少的队列，编号从0开始保证当存在多个最短队列时，选择编号最小的
            if(window[i].poptime < minpoptime){
                idx = i;
                minpoptime = window[i].poptime;
            }
        }
        Pnode& W = window[idx];  //引用，用W代替window[idx]，行文方便
        W.q.pop();
        W.q.push(pos);
        W.endtime += need[pos];
        W.poptime += need[W.q.front()];
        ans[pos] = W.endtime;
    }
    for(int i = 0; i < query; i++){ 
        scanf("%d", &q);
        if(ans[q - 1] - need[q - 1] >= convert(17, 0)) printf("Sorry\n"); //服务开始时间达到17：00，输出Sorry。否则输出服务结束时间。
        else printf("%02d:%02d\n",ans[q-1]/60, ans[q - 1]%60);
    }
    return 0;
}