PAT甲级-1014 Waiting in Line

题目

题目大意

一个银行有n个窗口，每个窗口最多站m个人，其余人在黄线外等候。假设k个人同时进入银行按先后次序排队，每个人都有相应的服务时间。每个顾客都选择最短队列站，如果有多个相同长度的队列，按序号小的站。给出要查询的人的序号，要求输出该人结束服务的时间。如果顾客开始服务的时间晚于17:00，则输出Sorry。

思路

银行排队问题，根据题目模拟。先考虑数据结构，根据题目很容易想出队列，这里我直接用m行n列的二维数组来表示黄线内的位置，后续模拟先进先出的操作，也可以用vector<queue>来表示。

然后考虑计算方法，黄线内和黄线外的人选择位置的算法是不一样的。黄线内的人不需要等待，一个萝卜一个坑地按序就座。但黄线外的人由于前面的位置已满，需要等某一个人出来再站空位置上。怎么知道哪个窗口的人先出来，就要看每一个队列中第一个人服务完成需要的时间。

找到首元素时间最小的那个队列，假设时间为t，让该元素出队，下一个人就能入队。出队就意味着此时已经过了t时间，因此其余队列的首元素都要减去t，按照题目中给的例子，如下图所示：

用time数组记录每个人所需的服务时间，query数组记录要查询的人的编号。元素出队意味着经过了一段时间，下一个元素入队还需要加上经过的这段时间，因此需要用sum数组累加已经经过的时间。 初始化每个队列的时间为0，每入队一个，就累加时间，该元素的服务完成时间res[i]就等于sum[j]加上time[i]。如果某个元素入队前的sum已经超过540分钟，则该元素开始时间晚于17:00，不能被服务。可以用sorry数组来记录每个元素是否能被服务。每个人的服务完成时间另用一个res数组来记录。

注意，测试点1和测试点2运行时错误，是因为没有考虑人数小于n*m的情况。在循环条件中加上人数上限即可。

代码

#include <iostream>
#include <vector>
#include <queue>
#include <climits>
using namespace std;

int main(){
    int n, m, k, q;
    cin >> n >> m >> k >> q;
    vector<int> time(k);  // 每个人要花费的时间
    vector<int> query(q);  // 要查询的人的编号
    for (int i = 0; i < k; i++){
        cin >> time[i];
    }
    for (int i = 0; i < q; i++){
        cin >> query[i];
    }

    vector<vector<int>> v(m, vector<int>(n));  // 二维数组，包含n个队列，每个队列长为m
    vector<int> sum(k, 0);  // 计算当前列需要花费的总时间
    vector<int> res(k, 0);  // 每个人完成的时间
    vector<bool> sorry(k, false);  // 是否不能被服务

    int index = 0;  // index为当前人的索引
    for (int i = 0; i < m && index < k; i++){  // 要加上条件index < k，否则测试点1和测试点2显示运行时错误。考虑人数小于n * m的情况
        for (int j = 0; j < n && index < k; j++){
            v[i][j] = time[index];
            if (sum[j] >= 540){
                sorry[index] = true;
            }
            sum[j] += time[index];
            res[index] += sum[j];
            index++;
        }
    }

    for (int i = index; i < k; i++){  // i为当前人的索引
        int minj = 0;  // 首元素最小的队列的索引
        int mintime = INT_MAX;
        for (int j = 0; j < n; j++){
            if (mintime > v[0][j]){
                mintime = v[0][j];
                minj = j;
            }
        }
        res[i] = sum[minj] + time[i];
        for (int j = 0; j < n; j++){
            if (j != minj){
                v[0][j] -= v[0][minj];
            }
        }  // 更新其它列的首元素
        for (int t = 0; t < m - 1; t++){
            v[t][minj] = v[t + 1][minj];
        }
        v[m - 1][minj] = time[i];  // 更新要插入列的首元素
        if (sum[minj] >= 540){
            sorry[i] = true;
        }
        sum[minj] += time[i];
    }

    for (int i = 0; i < q; i++){
        if (sorry[query[i]-1] == true){
            cout << "Sorry" << endl;
        }else{
            int hour = 8 + res[query[i]-1] / 60;
            int minute = res[query[i]-1] % 60;
            printf("%02d:%02d\n", hour, minute);
        }
    }

    return 0;
}
/*
在黄线内的人不需要等待，只有在黄线外的才需要等待并计算最短队列
*/