原题回顾

PAT_A1017原文链接

1017 Queueing at Bank (25分)

作者: CHEN, Yue
单位: 浙江大学
时间限制: 400 ms
内存限制: 64 MB
代码长度限制: 16 KB

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₄) - 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

解题思路及注意点

• 首先想到的是用简单模拟来做，模拟时间递增，以秒为单位。其中有几点需要特别注意：

1. 模拟截止时间并非17:00，而是在17:00及之前来的客户全部离开等待区之时，否则测试点5将会不通过，该测试点就包含在17:00之前到达但是处理时间拖到了17:01以后；
2. 在17:00之前来的客户，不论在等待区等到什么时候，银行总会等到为其服务，等待时间必须加到结果之中，即时是一万年也要等。

• 第二种就是用排序来解决，将窗口服务时间列为数组，每次通过排序来得到最早服务的窗口，通过判断客户到达时间与窗口服务时间的关系来计算等待时间。这里的截止条件只有判断客户的到达时间是否超过17:00，而与客户的业务开始处理时间无关。

代码部分

模拟：

#include <cstdio>
#include <queue>
#include <algorithm>
using namespace std;
const int maxn = 10010;

struct record
{
    int hh, mm, ss;
    int process;
} rec[maxn], temp;

int n, k; //总人数，窗口数
int realN = 0; //实际服务人数
queue<record> line; //等待区队列
int waitTime = 0; //等待总时间
int window[110];  //窗口当前用户剩余处理时间，0为无用户

bool cmp(record a, record b) //将数据按照到达的时间排序
{
    if (a.hh != b.hh)
        return a.hh < b.hh;
    else if (a.mm != b.mm)
        return a.mm < b.mm;
    else
        return a.ss < b.ss;
}

void get_ans()
{
    int hh = 0, mm = 0, ss = 0; //时，分，秒
    int st = 0; //当前第一位到达的人编号
    bool isWindow; //是否有空窗口
    while ((hh < 17 || mm < 0 || ss < 0) || !line.empty())
    {
        // 银行关门之前或者排队队列为空
        ss++; //当前时间+1s
        isWindow = false;
        for (int i = 0; i < k; i++) //如果窗口有人则处理时间--，有空窗口则isWindow置为true
        {
            if (window[i] > 0)
            {
                window[i]--;
            }
            if (window[i] == 0)
                isWindow = true;
        }
        if (ss == 60)
        {
            ss = 0;
            mm++;
        }
        if (mm == 60)
        {
            mm = 0;
            hh++;
        }
        if (hh == rec[st].hh && mm == rec[st].mm && ss == rec[st].ss && (hh < 17 || mm < 0 || ss < 0))
        {
            // 在17:00之前有人到达银行
            line.push(rec[st]); //进入排队队列
            realN++; //实际处理人数++
            st++; //到达的人编号++
        }
        if (hh > 7 && isWindow == true && !line.empty())
        {
            // 到营业时间，有空窗口，有人排队
            for (int i = 0; i < k; i++) //找到空窗口，等待区进入窗口
            {
                if (window[i] == 0 && !line.empty())
                {
                    window[i] = line.front().process * 60;
                    line.pop();
                }
            }
        }
        waitTime += line.size(); //当前等待区的总等待时间（总等待人数*1s）
    }
}

int main()
{
    scanf("%d%d", &n, &k);
    for (int i = 0; i < n; i++)
    {
        scanf("%d:%d:%d", &rec[i].hh, &rec[i].mm, &rec[i].ss);
        scanf("%d", &rec[i].process);
    }
    sort(rec, rec + n, cmp);
    fill(window, window + 110, 0);
    get_ans();
    printf("%.1f\n", waitTime / 60.0 / realN);
    return 0;
}

排序：

//PAT_A1017
#include <iostream>
#include <vector>
#include <cstdio>
#include <algorithm>
using namespace  std;
const int maxn = 1010;
struct node {
    int st;
    int wt;
    node(int _st, int _wt):st(_st), wt(_wt){}
};
bool cmp (node a, node b) {
    return a.st < b.st;
}
vector<node> customer;
vector<int> window;

int main () {
    int n, k, num = 0;
    double ans = 0.0;
    scanf("%d%d", &n, &k);
    for (int i = 0; i < n; i++) {
        int h, m, s, st, wt;
        scanf("%d:%d:%d %d", &h, &m, &s, &wt);
        st = h * 60 * 60 + m * 60 + s;
        //wt = (wt > 60 ? 60 : wt); //处理超过一个小时的一律压缩至一小时，不过测试点中没有体现
        wt *= 60;
        customer.push_back(node(st, wt));
    }
    sort(customer.begin(), customer.end(), cmp);
    for (int i = 0; i < k; i++) { //初始化窗口服务时间，均为8:00
        window.push_back(8 * 60 * 60);
    }
    for (int i = 0; i < n; i++, num++) {
        sort(window.begin(), window.end()); //取当前窗口服务结束的最早时间放至首位
        if (customer[i].st > 17 * 60 * 60) { //break条件只有客户到达时间是否超过17:00，与客户开始处理的时间无关
            break;
        }
        if (customer[i].st < window[0]) { //早于窗口服务时间到达
            ans += window[0] - customer[i].st; //加上等待时间
        }
        if (customer[i].st < window[0]) {
            window[0] = window[0] + customer[i].wt; //下次窗口服务时间为当前窗口服务结束时间加上该等待用户的处理时间
        } else {
            window[0] = customer[i].st + customer[i].wt; //当前有空余窗口,下次服务时间为客户到达时间加处理时间，无需等待
        }
    }
    ans /= 60.0 * num;
    printf("%.1f", ans);
    return 0;
}