浙大 PAT 甲级 1017 Queueing at Bank C++

思路

跟1014题很像，也是一道模拟排队题。区别在于1014侧重单入口多出口的排队，默认所有人都在开始时刻开始排队，而1017题黄线前的若干条队伍每队只能容纳1人，并且考虑不同时刻的到达。

数据结构考虑一个结构体Customer代表排队的人，两个成员变量：到达时间、业务办理所需时长。用一个vector<Custmoer>代表队列，sort函数(#include<algorithm>)使其按照到达时间排序即可。还有一个整型数组，下标代表窗口编号，其值代表每个窗口恢复空闲的时刻，最开始为八点，过程中为占用这个窗口的用户的到达时间加上其业务所需时长。

以上是大致思路，还有两个细节需要考虑：

• 17:00及以后到达的，不能加入vector，直接忽略即可。
• 8:00以前到达的，如果把算法写的具有普遍性，那么这一点就完全不需要考虑。我的做法是，定义一个标记变量bool nowait，把客户分成经历了等待时间的，和未经历等待时间的，分别处理，这样算法就可能会简单一些。

代码

#include<stdio.h>
#include<vector>
#include<algorithm>
using namespace std;

struct Customer
{
    int atime;
    int ptime;
};
vector<Customer> lines;
int windows[100];

bool cmp(Customer a, Customer b)
{
    return a.atime < b.atime;
}

int main()
{
    int N, K;
    scanf("%d%d", &N, &K);
    for (int i = 0; i < N; i++)
    {
        int h, m, s, p;
        scanf("%d:%d:%d%d", &h, &m, &s, &p);
        Customer c;
        c.atime = h * 3600 + m * 60 + s;
        c.ptime = p;
        if (c.atime < 17 * 3600)
        {
            lines.push_back(c);
        }
    }
    for (int i = 0; i < K; i++)
    {
        windows[i] = 8 * 3600;
    }
    sort(lines.begin(), lines.end(), cmp);
    float sum = 0;
    for (int i = 0; i < lines.size(); i++)
    {
        bool nowait = false;
        int min = 10000000;
        int w = -1;
        for (int j = 0; j < K; j++)
        {
            if (windows[j] < lines[i].atime)
            {
                windows[j] = lines[i].atime + lines[i].ptime * 60;
                nowait = true;
                break;
            }
            if (windows[j] < min)
            {
                min = windows[j];
                w = j;
            }
        }
        if (!nowait)
        {
            sum += windows[w] - lines[i].atime;
            windows[w] += lines[i].ptime * 60;
        }
    }
    printf("%.1f", sum / 60.0 / (float)lines.size());
    return 0;
}