题解 UVA822 【Queue and A】

核心部分的逻辑是将所有要发生的事情用事件来表示，用优先级队列来维护所有的事件，循环着每次从中取出最早的一个事件，然后按照时间类型进行分类处理：

struct Event
{
    int time, id;
    bool isRorC; // 是请求到达还是客服空闲事件
};

输入时，每种请求就实现生成num个事件放到事件队列中。模拟的循环中，每个时间点，用multiset<int>作为要服务的请求队列，使用multiset是因为队列中可能用相同主题的请求。同时用一个set维护空闲的客服编号。

首先取出所有时间相同的队首事件，挨个进行处理。

1. 如果是请求事件，就放到请求队列。
2. 如果是客服事件，就将客服加到空闲客服集合中。

然后就是针对当前空闲客服以及请求队列中的请求进行匹配处理。

while (请求队列非空 && 空闲客服集合非空)
{
    (1) 针对每个请求建立一个集合set<int>，放置所有可以服务此请求的客服编号，编号排序规则参考题目的表述。
    (2) 先将每个客服按照优先级分配到其能处理的每个任务的集合中。
    (3) 如果没有进行匹配，直接退出while循环。
    (4) 按照之前分配好的任务集合给客服分配任务，对于每个分配好的客服，要构造一个其变为空闲的事件，放入事件队列。
}

完整程序如下：

#include <algorithm>
#include <iostream>
#include <queue>
#include <cmath>
#include <set>
#include <map>
using namespace std;
const int maxn = 21, maxm = 8;

struct Event
{
    int time, id;
    bool isRorC;
    bool operator<(const Event &rhs) const { return time > rhs.time; }
    Event(int t, int i, bool isr = true) : time(t), id(i), isRorC(isr) {}
};

struct ReqInfo
{
    int tid, num, t0, t, dt;
} reqs[maxn];

struct StaffInfo
{
    int tids[maxn], pid, k, idx, last, req;
    bool operator<(const StaffInfo &rhs) const
    {
        return last < rhs.last || (last == rhs.last && pid < rhs.pid);
    }
} staffs[maxm];

struct Comp
{
    bool operator()(int lhs, int rhs) const { return staffs[lhs] < staffs[rhs]; }
};

multiset<int> rQs;
priority_queue<Event> em;
set<int> freeStaffs;
set<int, Comp> rt[maxn];
int n, m, kase = 0;

void solve()
{
    int Time = em.top().time;
    while (!em.empty() && Time == em.top().time)
    {
        const auto &e = em.top();
        if (e.isRorC)
            rQs.insert(e.id);
        else
            freeStaffs.insert(e.id);
        em.pop();
    }
    while (!rQs.empty() && !freeStaffs.empty())
    {
        for (int i = 0; i < n; i++)
            rt[i].clear();
        bool canAssign = false;
        for (auto &i : freeStaffs)
        {
            auto &si = staffs[i];
            for (int j = 0; j < si.k; j++)
            {
                int tid = si.tids[j];
                if (!rQs.count(tid))
                    continue;
                canAssign = true;
                rt[tid].insert(si.idx);
                break;
            }
        }
        if (!canAssign)
            break;
        for (int i = 0; i < n; i++)
        {
            auto &ss = rt[i];
            while (rQs.count(i) && !ss.empty())
            {
                rQs.erase(rQs.find(i));
                int si = *(ss.begin());
                auto &s = staffs[si];
                s.last = Time;
                em.push(Event(Time + reqs[i].t, s.idx, false));
                freeStaffs.erase(s.idx);
                ss.erase(si);
            }
        }
    }
    if (em.empty())
        cout << "Scenario " << ++kase << ": All requests are serviced within " << Time << " minutes." << endl;
}

int main()
{
    map<int, int> tids;
    while (cin >> n && n)
    {
        freeStaffs.clear(), tids.clear(), rQs.clear();
        for (int i = 0; i < n; i++)
        {
            auto &r = reqs[i];
            cin >> r.tid >> r.num >> r.t0 >> r.t >> r.dt;
            tids[r.tid] = i;
            r.tid = i;
            for (int j = 0; j < r.num; j++)
                em.push(Event(r.t0 + r.dt * j, i));
        }
        cin >> m;
        for (int i = 0; i < m; i++)
        {
            auto &s = staffs[i];
            cin >> s.pid >> s.k;
            for (int j = 0; j < s.k; j++)
            {
                cin >> s.tids[j];
                s.tids[j] = tids[s.tids[j]];
            }
            s.last = 0;
            s.idx = i;
            em.push(Event(0, s.idx, false));
        }
        while (!em.empty())
            solve();
    }
    return 0;
}

此类离散事件模拟类的题目最关键是要掌握事件概念的抽象方法以及优先级队列的使用。UVa212也是一个很好的此类题目。