[刷题]算法竞赛入门经典(第2版) 5-13/UVa822 - Queue and A

时间：2022-08-08 05:01:00

题意：模拟客服MM，一共有N种话题，每个客服MM支持处理其中的i个（i < N），处理的话题还有优先级。为了简化流程方便出题，设每个话题都是每隔m分钟来咨询一次。现知道每个话题前来咨询的时间、间隔、处理此话题所需的时长与一共有多少次咨询。问多少时间后全部话题处理完成。

代码：（Accepted，0.010s）

//UVa822 - Queue and A

//Accepted 0.010s

//#define _XIENAOBAN_

#include<algorithm>

#include<iostream>

#include<vector>

#include<queue>

#include<map>

#define MI 2147483647

using namespace std;

struct T {

    int ti; //time for per task

    queue<int> table;

} ttmp;

struct P {

    int id, at, st, n, to[22];//identity, available time, start time of last task, number of topics, topics

    bool operator< (const P& that) const {

        if (st != that.st) return st < that.st;

        return id < that.id;

    }

} ptmp;

int Tpc, Psnl;//Number of Topics & Personnel

int name, num, nt, to, Scenario(0);

int main()

{

#ifdef _XIENAOBAN_

#define gets(T) gets_s(T, 80)

    freopen("in.txt", "r", stdin);

#endif

    ptmp.at = 0;

    while (scanf("%d", &Tpc) != EOF && Tpc != 0) {

        int time(MI), needtime(0);

        map<int, T> tpc;

        for (int i(0);i < Tpc;++i) {

            scanf("%d%d%d%d%d", &name, &num, &nt, &ttmp.ti, &to);

            if (time > nt) time = nt;

            auto& now(tpc[name] = ttmp);

            for (int i(0);i < num;++i)

                now.table.push(nt), nt += to;

        }

        scanf("%d", &Psnl);

        vector<P> psnl(Psnl);

        for (int i(0);i < Psnl;++i) {

            scanf("%d%d", &ptmp.id, &ptmp.n);

            for (int j(0);j < ptmp.n;++j)

                scanf("%d", ptmp.to + j);

            psnl[i] = ptmp;

        }

        while (Tpc) {

            int jumpt = MI;//Jump time to the earliest possible available time of all the men

            sort(psnl.begin(), psnl.end());

            for (auto& p : psnl) {//For all staff members

                int pti(MI);//Man's earliest possible available time

                if (p.at > time) pti = p.at;//Man is busy

                else {                      //Man is available

                    for (int i(0);i < p.n;++i) {//For all topics that man can handle

                        auto& t(tpc[p.to[i]]);

                        if (t.table.empty()) continue;                          //Man find current topic finished

                        if (t.table.front() <= time) {                          //Man find his topic

                            pti = time + t.ti;

                            if (needtime < pti) needtime = pti;

                            p.st = time;

                            t.table.pop();

                            if (t.table.empty()) --Tpc;

                            break;

                        }

                        else if (t.table.front() < pti) pti = t.table.front();  //Man find current topic will be available at t.table.front()

                    }

                    p.at = pti;

                }

                if (pti < jumpt) jumpt = pti;

            }

            time = jumpt;

        }

        printf("Scenario %d: All requests are serviced within %d minutes.\n", ++Scenario, needtime);

    }

    return 0;

}

分析：每分钟每分钟的模拟的话就有点慢了。我的做法是：

对每个topic，把它们每次过来询问的时间放在queue里，每开始处理一件就pop一件，直到它empty则说明处理完毕。

对每个员工，找出他的下一次“开始空闲”或“可能有事情做”的时间pti。所谓“开始空闲”或“可能有事情做”的时间是指：

  1. 若这人正在处理一个topic，则pti=处理完本topic的时间，这叫“开始空闲”；
  2. 若这人闲着，则给他找活干，若找到了可处理topic，pti=处理完这个topic的时间，也是“开始空闲”；
  3. 若这人闲着，但发现无活可干，每个他可以处理的topic都还没到来，那么他的pti=最快到来的下一个topic的时间，即只有topic来了他才可能“可能有事情做”。之所以是“可能”，因为每次都要按照“上一次开始干活的时间与ID”把每个人排序，所以他的活可能被抢，依然是“无事可干”状态。
  4. pti初始化时为int的最大值。只有当该员工的每个topic全都处理完的状态时，pti全程没有被赋值，于是该员工的下一个空闲时间变成无限大，一定程度上相当于以后的模拟运算就不考虑他了。

找出了每个人的pti，让时间跳转到最近的一个pti，进行下一次循环（要注意的是time最终跳出循环时可能不等于所需时间，所以又定义了个needtime）。

这题最坑的是，udebug的算法是错误的(⊙﹏⊙)。它的数据答案我死活对不上，害的我调试了好几天。。。后来去网上找别人的算法，发现结果和udebug也一大半数据对不上。但是提交后就AC了。（这uva的数据也比较水，udebug上的100个测试数据我运算了蛮慢的，但提交上去就0.010s。不过开心的是我的运算比网上找的那几个算法都快。）

相关文章