题意：模拟客服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。所谓“开始空闲”或“可能有事情做”的时间是指：
若这人正在处理一个topic，则pti=处理完本topic的时间，这叫“开始空闲”；若这人闲着，则给他找活干，若找到了可处理topic，pti=处理完这个topic的时间，也是“开始空闲”；若这人闲着，但发现无活可干，每个他可以处理的topic都还没到来，那么他的pti=最快到来的下一个topic的时间，即只有topic来了他才可能“可能有事情做”。之所以是“可能”，因为每次都要按照“上一次开始干活的时间与ID”把每个人排序，所以他的活可能被抢，依然是“无事可干”状态。pti初始化时为int的最大值。只有当该员工的每个topic全都处理完的状态时，pti全程没有被赋值，于是该员工的下一个空闲时间变成无限大，一定程度上相当于以后的模拟运算就不考虑他了。找出了每个人的pti，让时间跳转到最近的一个pti，进行下一次循环（要注意的是time最终跳出循环时可能不等于所需时间，所以又定义了个needtime）。
这题最坑的是，udebug的算法是错误的(⊙﹏⊙)。它的数据答案我死活对不上，害的我调试了好几天。。。后来去网上找别人的算法，发现结果和udebug也一大半数据对不上。但是提交后就AC了。（这uva的数据也比较水，udebug上的100个测试数据我运算了蛮慢的，但提交上去就0.010s。不过开心的是我的运算比网上找的那几个算法都快。）
转载于:https://www.cnblogs.com/xienaoban/p/6798081.html
相关资源：数据结构—成绩单生成器