1014 Waiting in Line

狗逼模拟——之二

本题和上一题有些类似,也是对队列的模拟,所以放在一起讲一下。

题面

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.
  • Customeri​​ will take Ti​​ 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, customer​1​​ is served at window​1​​ while customer​2​​ is served at window​2​​. Customer​3​​ will wait in front of window​1​​ and customer​4​​ will wait in front of window​2​​. Customer​5​​ will wait behind the yellow line.

At 08:01, customer​1​​ is done and customer​5​​ enters the line in front of window​1​​ since that line seems shorter now. Customer​2​​ will leave at 08:02, customer​4​​ 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

本题和上题不一样的点在于:每个窗口前还有一个能容纳m个人的队列,本题的来客是没有到来时间的,并且本题要记录每个用户完成服务时的时间,而非等待时间。

注意本题和上一题一样,我们只拒绝17:00之后到达窗口的顾客,而在17:00之前到达窗口的顾客,我们还是会给他服务,不论这个服务会持续多久。

要用到的基本数据结构也和上题差不多,不过除了用以描述客户数据的结构体cus、客户数组cus_list[]和用以记录该窗口结束服务时间的int windows[] 数组之外,还需要每个窗口之前的队列 queue<cus> lines[](答案这里是把窗口单独写了一个结构体,其实原理类似),不过要注意到本题原理上要知道每一个客户的结束服务时间,所以需要准备一个数据结构来储存每个客户的结束服务时间(这里我偷懒复用了cus结构体里的last字段来保存结束服务时间,虽然对于本题来说原理上没有错误,但不是一个好习惯)。
还有一点就是,因为出队时相对于入队顺序是乱序的,因此并不能知道出队的客户属于原cus_list[]的哪一个客户,所以要在cus结构体里加一个用于保存原数组下标的字段id;

其实这一题很有迷惑性,我们不应该从所有队列为空时就开始服务,而是需要首先将窗口以及窗口之前的队列填满,然后如果还剩下客人没有进入黄线,则再开始入队服务。
入队的过程和上题基本一样,都是先找到“未来”最先结束服务的窗口(“未来”结束服务的时间=“当前”结束服务的时间+队首last)(且小下标优先),然后把队首元素出队,将下一个等待的顾客入队(此时“最短的队列”必然就是最先结束服务的队列,因为其他队列都是满的),甚至都不需要另写函数找最短长度的队列。(然而一开始我写了,并成功把自己绕晕)
当所有客人都已进入黄线时,此时每一个客人何时结束服务都已经敲定,那么挨个儿队列处理一下队列中的客人即可。

这题我没有仔细看标答了(因为感觉标答写得有点长,猜测不是很好),由于一开始没有想清楚所以代码里写了很多没有用的分支判断,如下所示:

// 硬模拟
#include <cstdio>
#include <iostream>
#include <queue>
#define MAXN 1000
#define INFI 100001
using namespace std;

int windows[MAXN];
int ans[MAXN];
int n, m, k, q;

struct cus
{
    int id;
    int last;
} cus_list[MAXN];
queue<cus> lines[MAXN];

void trans(int l)
{
    int HH = (l / 60) + 8;
    int MM = l % 60;
    if (l == -1)
    {
        printf("Sorry\n");
    }
    else
        printf("%02d:%02d\n", HH, MM);
}
int main()
{
    cin >> n >> m >> k >> q;

    // 初始化
    for (int i = 0; i < k; i++)
    {
        cin >> cus_list[i].last;
        cus_list[i].id = i;
    }

    // 1. 先填充黄线内每个窗口的队列,要分是否有客人剩余的情况(防止数组溢出)
    for (int i = 0; i < n * m; i++)
    {
        if (i >= k)
        {
            break;
        }
        lines[i % n].push(cus_list[i]);
    }
    // 2. 如果还有客人剩余,剩下的客人进行入队服务
    for (int i = n * m; i < k; i++)
    {
        int mini = 0;
        int min = INFI;
        int f = 0;
        for (int i = 0; i < n; i++)
        {
            // 注意这里是找“未来”最先结束的窗口,每个窗口的“未来”结束时间应当是“当前”结束时间+队首客人的持续时间
            f = lines[i].empty() ? 0 : lines[i].front().last;
            if (min > windows[i] + f)
            {
                min = windows[i] + f;
                mini = i;
            }
        }
        if (!lines[mini].empty())
        {

            if (windows[mini] >= 540) // 注意这里相当于是在判断“当前队首的客户是否在下班前接受了服务?”)
            {
                windows[mini] += lines[mini].front().last;
                cus_list[lines[mini].front().id].last = -1; // 如果超出下班时间,则将last赋成一个不可能的值
            }
            else
            {
                windows[mini] += lines[mini].front().last;
                cus_list[lines[mini].front().id].last = windows[mini];
            }
            lines[mini].pop();
        }
        if (lines[mini].size() < m)
        {
            lines[mini].push(cus_list[i]);
        }
    }

    // 3. 至此所有客人都已进入黄线内,挨个儿队列进行出队处理
    for (int i = 0; i < n; i++)
    {
        while (!lines[i].empty())
        {
            if (windows[i] >= 540)
            {
                windows[i] += lines[i].front().last;
                cus_list[lines[i].front().id].last = -1;
            }
            else
            {
                windows[i] += lines[i].front().last;
                cus_list[lines[i].front().id].last = windows[i];
            }
            lines[i].pop();
        }
    }
    // 输出询问
    for (int i = 0; i < q; i++)
    {
        int qq;
        cin >> qq;
        trans(cus_list[qq - 1].last);
    }
    return 0;
}

ok了家人们,今晚先不写最后一篇了,等着明天出去打桌游+吃海底捞,耶!

Subscribe
提醒
guest
0 评论
Inline Feedbacks
View all comments