PAT 1014 Waiting in Line (30分) STL queue

题目 Suppose a bank has N windows open for service. There is a yellow line in front of the windows which devides the waiting area into two parts. The rules for the customers to wait in line are:

• The space inside the yellow line in front of each window is enough to contain a line with M customers. Hence when all the N lines are full, all the customers after (and including) the (NM+1)st one will have to wait in a line behind the yellow line.
• Each customer will choose the shortest line to wait in when crossing the yellow line. If there are two or more lines with the same length, the customer will always choose the window with the smallest number.
• Customer[​i] will take T[​i] minutes to have his/her transaction processed.
• The first N customers are assumed to be served at 8:00am.

Now given the processing time of each customer, you are supposed to tell the exact time at which a customer has his/her business done.

For example, suppose that a bank has 2 windows and each window may have 2 customers waiting inside the yellow line. There are 5 customers waiting with transactions taking 1, 2, 6, 4 and 3 minutes, respectively. At 08:00 in the morning, customer1 is served at window1 while custome​2​​ is served at window2. Customer ​3 will wait in front of window​1​​ and customer​4​​ will wait in front of window2. Customer​5​​ will wait behind the yellow line.

At 08:01, customer1 is done and customer​5​​ enters the line in front of window1 since that line seems shorter now. Customer2​​ will leave at 08:02, customer4​​ at 08:06, customer​3​​ at 08:07, and finally customer​5​​ at 08:10.

Input Specification: Each input file contains one test case. Each case starts with a line containing 4 positive integers: N (≤20, number of windows), M (≤10, the maximum capacity of each line inside the yellow line), K (≤1000, number of customers), and Q (≤1000, number of customer queries).

The next line contains K positive integers, which are the processing time of the K customers.

The last line contains Q positive integers, which represent the customers who are asking about the time they can have their transactions done. The customers are numbered from 1 to K.

Output Specification: For each of the Q customers, print in one line the time at which his/her transaction is finished, in the format HH:MM where HH is in [08, 17] and MM is in [00, 59]. Note that since the bank is closed everyday after 17:00, for those customers who cannot be served before 17:00, you must output 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个窗口，每个窗口前可以排队m人。
• 有k位用户需要服务，给出了每位用户服务需要占用的的minute数。
• 银行在8点开始服务，如果有窗口还没排满就在窗口前排队，否则就在黄线外等候。如果有某一队列有一个用户走了服务完毕了，黄线外的人就进来一个。如果同时有多个窗口走了一个人，就选窗口数最小的那个窗口前去排队。
• 要求输入q个人，以HH:mm的格式输出他们的服务结束时间。银行在17:00点停止服务，如果一个客户在17:00以及以后还没有开始服务（此处不是结束服务是开始17:00）就输出Sorry。

易错点分析

这个题最易错的地方是如何判断一个客户无法完成服务，

是看他的结束时间是否超过17：00吗？？不不不不不，只要他在17：00前开始被服务，银行就必须给他服务完才结束下班。所以我们要看他的开始服务时间是不是超过17：00，而不是结束时间！！！

解题思路

• 既然是排队，那么当然要用队列了，每个窗口前都有一个队，假如有n个窗口，那就建n个队列呗，但是因为编号都是从1开始，所以直接建n+1个队列好了
• 使用结构体来保存顾客的信息，包括==开始服务时间==、==服务花费时间==、==结束服务时间==，这样我们最后只需要看他的开始服务时间是否超过17：00就可以了。
• 字符串形式时间不好判断，题目中给出的是以分钟为单位的，那么我们直接用int保存就可以了，8：00就相当于8*60，17：00就相当于17*60，最后输出HH:mm很好办printf("%02d:%02d\n", customer[id].end_time / 60, customer[id].end_time % 60);
• 首先银行开始服务，每个窗口前可以排m个人，那么前n*m个人可以直接排到黄线前面，所以这部分人要单独处理，后面的人才需要等前面有人走了再去排队。
• 对于黄线后面的人，逐个分析，首先判断所有窗口前的队列中的队首元素，看那个人的服务结束时间，找到最早的那个，让那个人出队，然后他排到这条队伍后面，这就相当于实现了题目中他总是选择排到最短的队伍后面

满分代码

个人觉得我代码注释够清楚了，应该都能看懂的吧，哈哈。

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

struct Customer {
    int cost_time, start_time, end_time;
} customer[1001];

int main() {

    // n个窗口，每个窗口到黄线，最多排m个人，k个客户，有q个客户想知道他啥时候被服务结束
    int n, m, k, q;
    cin >> n >> m >> k >> q;
    // 银行开始服务时间，结束服务时间
    int open_time = 8 * 60, close_time = 17 * 60;
    // n个窗口，从1开始
    queue<Customer> windows[n + 1];

    // 读入k个人花费的时间
    for (int i = 1; i <= k; ++i)
        cin >> customer[i].cost_time;
    // 排队
    for (int i = 1; i <= k; ++i) {
        // 黄线内能排 n * m个人
        if (i <= n * m) {
            // 按顺序挨个窗口，顾客id和窗口id都从1开始
            int window = (i - 1) % n + 1;
            // 前n个人，一人一个窗口
            if (i <= n) {
                // 开始时间是银行开始服务时间
                customer[i].start_time = open_time;
                // 他的结束时间是他的开始加+他的服务时间
                customer[i].end_time = open_time + customer[i].cost_time;
            } else {
                Customer last_customer = windows[window].back();
                // 他的开始时间是上一个人的结束时间
                customer[i].start_time = last_customer.end_time;
                // 他的结束时间是他的开始加+他的服务时间
                customer[i].end_time = customer[i].start_time + customer[i].cost_time;
            }
            // 排到对应窗口
            windows[window].push(customer[i]);
        // 黄线外的人
        } else {
            // 看哪一个窗口先离开一个人，就是看每个窗口前那个队伍中第一个人的离开时间
            int window = 1;
            for (int j = 2; j <= n; ++j) {
                // 除非第一个人离开的更早，才选择这个窗口
                if (windows[j].front().end_time <
                    windows[window].front().end_time) {
                    window = j;
                }
            }
            // 这个窗口第一个人出队
            windows[window].pop();
            // 排到这个窗口
            Customer last_customer = windows[window].back();
            // 他的开始时间是上一个人的结束时间
            customer[i].start_time = last_customer.end_time;
            // 他的结束时间是他的开始加+他的服务时间
            customer[i].end_time = customer[i].start_time + customer[i].cost_time;
            //入队
            windows[window].push(customer[i]);
        }
    }
    // q个人想要查询自己什么时间能结束
    int id;
    while (q-- > 0) {
        cin >> id;
        // 开始服务时间超过了银行关门时间，无法服务
        if (customer[id].start_time >= close_time)
            cout << "Sorry" << endl;
        else
            printf("%02d:%02d\n", customer[id].end_time / 60,
                   customer[id].end_time % 60);
    }

    return 0;
}