1017 Queueing at Bank

狗逼模拟——之一

众所周或不那么周知,本菜逼一直很讨厌做大模拟之类的题目,其冗长复杂的题面、故意说得模棱两可的各种边界值坑和相得益彰的极为简洁的输入样本合起伙来折磨我的意志。经常是花了一晚上写出的代码只过一个样例点,于是信心满满到呜呼哀哉。

那不会做就得多练,所以本菜逼翻开《算法笔记》的“快乐模拟”一章,开启我的受苦之旅。

题面

Suppose a bank has K windows open for service. There is a yellow line in front of the windows which devides the waiting area into two parts. All the customers have to wait in line behind the yellow line, until it is his/her turn to be served and there is a window available. It is assumed that no window can be occupied by a single customer for more than 1 hour.

Now given the arriving time T and the processing time P of each customer, you are supposed to tell the average waiting time of all the customers.

Input Specification:

Each input file contains one test case. For each case, the first line contains 2 numbers: N (≤10​4​​) – the total number of customers, and K (≤100) – the number of windows. Then N lines follow, each contains 2 times: HH:MM:SS – the arriving time, and P – the processing time in minutes of a customer. Here HH is in the range [00, 23], MM and SS are both in [00, 59]. It is assumed that no two customers arrives at the same time.

Notice that the bank opens from 08:00 to 17:00. Anyone arrives early will have to wait in line till 08:00, and anyone comes too late (at or after 17:00:01) will not be served nor counted into the average.

Output Specification:

For each test case, print in one line the average waiting time of all the customers, in minutes and accurate up to 1 decimal place.

Sample Input:

7 3
07:55:00 16
17:00:01 2
07:59:59 15
08:01:00 60
08:00:00 30
08:00:02 2
08:03:00 10

Sample Output:

8.2

本题可以说是比较通俗的队列模拟了:只有一个队,m个服务窗口,有来客时间且乱序。但是要注意的是本题求的是“等待时间”,等待时间自然是不能把接受服务时的耗时算进去的。

结构体cus记录每个来客的到达时间和服务持续时间,数据保存在cus_list[]数组里,显然cus_list[]数组是要按照arrive来进行排序的(所以要随便写一个cmp,你懂的)。windows[]数组记录每个窗口结束服务的时间(即“下一个人要等到什么时候才可以接受服务”),同理也是每一轮要找到最先结束服务的(最小值),然后从排好序的cus_list[]数组中取出当前访问到的客户,让他接受服务。

接受服务包括结算等待时间加到输出上去并更新该窗口的结束服务时间(+该客户的last时间)。注意这里更新窗口结束服务的时间时不是

windows[mini] += cus_list[i].last

而是应该

windows[mini] = max(windows[mini], cus_list[i].arrive) + cus_list[i].last
因为要考虑到客户在结束服务之后没有立刻到达的情况

这点在一开始我没有考虑到。

还有就是当排好序的客户队列中一旦有一个人超出下班时间,那么后面的所有人都可以不计入计算(虽然这个无伤大雅)。&本题中只要在下班前开始服务,无论什么时候结束,该服务都会被算入总等待时间中,这点需要给予注意(已经是无情的加班机器了)。

除此之外就是日期转换和格式化输出之类的小问题了,注意的是”%.md”形式的格式化输出采取的是四舍六入五成双近似方式,如果题中要求“保留m位小数”则可以直接这么写,如果题目要求“四舍五入”则需要round()函数,直接舍去则是用先扩大10m 倍,然后转int舍去末尾项,再转double最后除10m 的方式处理。

下面是代码:

#include <cstdio>
#include <iostream>
#include <algorithm>
#define MAXN 10011
#define INFI 10000001
using namespace std;

struct cus
{
    int arrive;
    int last;
} cus_list[MAXN];

bool cmp(cus a, cus b)
{
    return a.arrive < b.arrive;
}

int windows[MAXN]; // 每个窗口结束服务的时间

int trans(char *s) // 时间转化
{
    int HH, MM, SS;
    sscanf(s, "%d:%d:%d", &HH, &MM, &SS);
    if (HH > 17 || (HH == 17 && (MM > 0 || SS > 0)))
    {
        return INFI;
    }
    return (HH - 8) * 3600 + MM * 60 + SS;
}
int main()
{
    int n, m;
    cin >> n >> m;
    int ans = 0;
    for (int i = 0; i < n; i++)
    {
        char s[10];
        cin >> s;
        cus_list[i].arrive = trans(s);
        cin >> cus_list[i].last;
    }
    sort(cus_list, cus_list + n, cmp);

    int gtz = 0;
    for (int i = 0; i < n; i++)
    {
        if (cus_list[i].arrive != INFI)
        {
            gtz++;          // 计数接受服务的顾客人数
            int min = INFI; // (不是好的命名习惯
            int mini = 0;
            for (int i = 0; i < m; i++) // 找最早结束服务的窗口
            {
                if (windows[i] < min)
                {
                    mini = i;
                    min = windows[i];
                }
            }
            int l = max(min, cus_list[i].arrive); // 下一个用户接受服务的时间点(注意这里不能直接l=min!)
            ans += (l - cus_list[i].arrive);
            windows[mini] = l + cus_list[i].last * 60;
        }
        else
        {
            break; // (标答这里做了优化,确实很对)由于队列有序,一旦有人超过下班时间,那么他们之后的人都不再提供服务
        }
    }
    if (gtz == 0) // 防止除零(似乎不需要考虑?)
    {
        printf("0");
        return 0;
    }

    printf("%.1f", (float)ans / gtz / 60);
    return 0;
}

还有两篇模拟,可能明后天会更新,敬请期待(虽然也只有我一个人会看就是了)。

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