本文主要是介绍习题5-13 客户中心模拟（Queue and A，ACM/ICPC World Finals 2000，UVa822），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
原题链接：https://vjudge.net/problem/UVA-822
分类：STL综合
备注：复杂模拟,阅读理解
前言：每种请求如果有多个可以同时被不同的客服所处理，一开始没理解这点疯狂WA。
但是巧的的有一份代码是每种请求同一时间只能被一个客服处理，并没有达到题意隐藏的这个要求却意外AC了？？甚至我认为这份代码对于客服挑选请求的顺序都可能不够严谨，这个AC能说明什么呢，UVa的数据太水吗？uDebug的那个负赞的数据有20多个可能是错的，我用自己的代码和别人的代码测试出错误数量不是完全一样，我的是23个，另一个人是25个，而我认为我错误却AC的代码测出uDebug错误的数据是67个和66个，对应下面贴的两份错误却AC代码。
只要注意了客服的排序以及客服id和客服顺序的映射，这题就没什么难点了。
我认为应该是正确AC(同种请求存在多个可以被多个客服同时处理)的代码如下:
#include<map>
#include<cstdio>
#include<algorithm>
using namespace std;
const int maxn = 20 + 5;
const int maxm = 5 + 5;struct CReq {int tid, num, t0, t, dt;
}req[maxn];struct CPer {int pid, k, tid[maxn], befst = 0;bool operator < (CPer x) {if (befst == x.befst)return pid < x.pid;return befst < x.befst;}
};int main(void) {int n, m, kase = 0;while (scanf("%d", &n) == 1 && n) {map<int, int>xb;for (int i = 0; i < n; i++) {scanf("%d%d%d%d%d", &req[i].tid, &req[i].num, &req[i].t0, &req[i].t, &req[i].dt);xb[req[i].tid] = i;}scanf("%d", &m);CPer per[maxm];map<int, CPer> pos;for (int i = 0; i < m; i++) {scanf("%d%d", &per[i].pid, &per[i].k);for (int j = 0; j < per[i].k; j++)scanf("%d", &per[i].tid[j]);pos[per[i].pid] = per[i];}sort(per, per + m);//预处理map<int, int>busy, run;//客服是否正在工作,客服的处理时间for (int i = 0; i < m; i++)busy[per[i].pid] = -1, run[per[i].pid] = 0;int ans = 0, flag = 1, hast[maxn] = { 0 }, arr[maxn] = { 0 };//开始处理,到达且未处理while (1) {flag = 0;for (int i = 0; i < n; i++)//判断是否第一个请求已经到达和后续请求的到达情况 if (hast[i]) {if (!req[i].num)continue;if ((ans - req[i].t0) % req[i].dt == 0) {arr[i]++;req[i].num--;}}else if (ans >= req[i].t0) {arr[i]++;hast[i] = 1;req[i].num--;}int bj[maxn] = { 0 };for (int i = 0; i < m; i++) {int now = per[i].pid;//客服的idif (busy[now] != -1) {int id = busy[now];//正在处理if (run[now] == req[id].t) {//处理完毕busy[now] = -1;}else run[now]++;}}for (int i = 0; i < m; i++) {int now = per[i].pid;//客服的idif (busy[now] == -1) {for (int j = 0; j < pos[now].k; j++) {int id = xb[pos[now].tid[j]];//请求的序号if (!arr[id])continue;pos[now].befst = per[i].befst = ans;busy[now] = id;arr[id]--;run[now] = 1;break;}}}sort(per, per + m);for (int i = 0; i < n; i++) {if (req[i].num || arr[i])//仍有未处理完或者正在处理的请求flag = 1; break;}for (int i = 0; i < m; i++) {int now = per[i].pid;//客服的idif (busy[now] != -1) { flag = 1; break; }}if (!flag)break;ans++;}printf("Scenario %d: All requests are serviced within %d minutes.\n", ++kase, ans);}return 0;
}
认为错误(一种请求在同一时间只能被一个客服处理)却AC的代码如下：
这里的代码同时还认为客服顺序的要求还不够严谨
#include<map>
#include<cstdio>
#include<algorithm>
using namespace std;
const int maxn = 20 + 5;
const int maxm = 5 + 5;struct CReq {int tid, num, t0, t, dt;
}req[maxn];struct CPer {int pid, k, tid[maxn], befst = 0;bool operator < (CPer x) {if (befst == x.befst)return pid < x.pid;return befst < x.befst;}
};int main(void) {int n, m, kase = 0;while (scanf("%d", &n) == 1 && n) {map<int, int>xb;for (int i = 0; i < n; i++) {scanf("%d%d%d%d%d", &req[i].tid, &req[i].num, &req[i].t0, &req[i].t, &req[i].dt);xb[req[i].tid] = i;}scanf("%d", &m);CPer per[maxm];map<int, CPer> pos;for (int i = 0; i < m; i++) {scanf("%d%d", &per[i].pid, &per[i].k);for (int j = 0; j < per[i].k; j++)scanf("%d", &per[i].tid[j]);pos[per[i].pid] = per[i];}sort(per, per + m);//预处理map<int, int>busy;for (int i = 0; i < m; i++)busy[per[i].pid] = -1;int ans = 0, flag = 1, hast[maxn] = { 0 }, arr[maxn] = { 0 }, run[maxn] = { 0 };//开始处理,到达且未处理,处理时间while (1) {flag = 0;for (int i = 0; i < n; i++)//判断是否第一个请求已经到达和后续请求的到达情况 if (hast[i]) {if (!req[i].num)continue;if ((ans - req[i].t0) % req[i].dt == 0) {arr[i]++;req[i].num--;}}else if (ans >= req[i].t0) {arr[i]++;hast[i] = 1;req[i].num--;}int bj[maxn] = { 0 };for (int i = 0; i < m; i++) {int now = per[i].pid;//客服的idif (busy[now] != -1) {int id = busy[now];//正在处理if (run[id] == req[id].t) {//处理完毕bj[id] = 1;busy[now] = -1;}else run[id]++;continue;}for (int j = 0; j < pos[now].k; j++) {int id = xb[pos[now].tid[j]];if (run[id])continue;if (!arr[id])continue;pos[now].befst = per[i].befst = ans;busy[now] = id;arr[id]--;run[id]++;break;}}for (int i = 0; i < n; i++)if (bj[i])run[i] = 0;for (int i = 0; i < m; i++) {int now = per[i].pid;if (busy[now] == -1) {for (int j = 0; j < pos[now].k; j++) {int id = xb[pos[now].tid[j]];if (run[id])continue;if (!arr[id])continue;pos[now].befst = per[i].befst = ans;busy[now] = id;arr[id]--;run[id]++;break;}}}sort(per, per + m);for (int i = 0; i < n; i++) {if (req[i].num || arr[i] || run[i])//仍有未处理完或者正在处理的请求flag = 1;}if (!flag)break;ans++;}printf("Scenario %d: All requests are serviced within %d minutes.\n", ++kase, ans);}return 0;
}
认为错误却AC，但客服排序更严谨的代码如下：
#include<map>
#include<cstdio>
#include<algorithm>
using namespace std;
const int maxn = 20 + 5;
const int maxm = 5 + 5;struct CReq {int tid, num, t0, t, dt;
}req[maxn];struct CPer {int pid, k, tid[maxn], befst = 0;bool operator < (CPer x) {if (befst == x.befst)return pid < x.pid;return befst < x.befst;}
};int main(void) {int n, m, kase = 0;while (scanf("%d", &n) == 1 && n) {map<int, int>xb;for (int i = 0; i < n; i++) {scanf("%d%d%d%d%d", &req[i].tid, &req[i].num, &req[i].t0, &req[i].t, &req[i].dt);xb[req[i].tid] = i;}scanf("%d", &m);CPer per[maxm];map<int, CPer> pos;for (int i = 0; i < m; i++) {scanf("%d%d", &per[i].pid, &per[i].k);for (int j = 0; j < per[i].k; j++)scanf("%d", &per[i].tid[j]);pos[per[i].pid] = per[i];}sort(per, per + m);//预处理map<int, int>busy;for (int i = 0; i < m; i++)busy[per[i].pid] = -1;int ans = 0, flag = 1, hast[maxn] = { 0 }, arr[maxn] = { 0 }, run[maxn] = { 0 };//开始处理,到达且未处理,处理时间while (1) {flag = 0;for (int i = 0; i < n; i++)//判断是否第一个请求已经到达和后续请求的到达情况 if (hast[i]) {if (!req[i].num)continue;if ((ans - req[i].t0) % req[i].dt == 0) {arr[i]++;req[i].num--;}}else if (ans >= req[i].t0) {arr[i]++;hast[i] = 1;req[i].num--;}int bj[maxn] = { 0 };for (int i = 0; i < m; i++) {int now = per[i].pid;//客服的idif (busy[now] != -1) {int id = busy[now];//正在处理if (run[id] == req[id].t) {//处理完毕run[id] = 0;busy[now] = -1;}else run[id]++;}}for (int i = 0; i < m; i++) {int now = per[i].pid;if (busy[now] == -1) {for (int j = 0; j < pos[now].k; j++) {int id = xb[pos[now].tid[j]];if (run[id])continue;if (!arr[id])continue;pos[now].befst = per[i].befst = ans;busy[now] = id;arr[id]--;run[id]++;break;}}}sort(per, per + m);for (int i = 0; i < n; i++) {if (req[i].num || arr[i] || run[i])//仍有未处理完或者正在处理的请求flag = 1;}if (!flag)break;ans++;}printf("Scenario %d: All requests are serviced within %d minutes.\n", ++kase, ans);}return 0;
}
这篇关于习题5-13 客户中心模拟（Queue and A，ACM/ICPC World Finals 2000，UVa822）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
