习题5-13 客户中心模拟（Queue and A，ACM/ICPC World Finals 2000，UVa822）

2024-04-13 03:32
文章标签 2000 模拟 13 icpc 中心 world 客户 acm queue 习题 finals uva822

本文主要是介绍习题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）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/899031。

相关文章

Java进阶13讲__第12讲_1/2

Java进阶13讲__第12讲_1/2

多线程、线程池 1.  线程概念 1.1  什么是线程 1.2  线程的好处 2.   创建线程的三种方式 注意事项 2.1  继承Thread类 2.1.1 认识  2.1.2  编码实现  package cn.hdc.oop10.Thread;import org.slf4j.Logger;import org.slf4j.LoggerFactory
阅读更多...
跨国公司撤出在华研发中心的启示：中国IT产业的挑战与机遇

跨国公司撤出在华研发中心的启示：中国IT产业的挑战与机遇

近日，IBM中国宣布撤出在华的两大研发中心，这一决定在IT行业引发了广泛的讨论和关注。跨国公司在华研发中心的撤出，不仅对众多IT从业者的职业发展带来了直接的冲击，也引发了人们对全球化背景下中国IT产业竞争力和未来发展方向的深思。面对这一突如其来的变化，我们应如何看待跨国公司的决策？中国IT人才又该如何应对？中国IT产业将何去何从？本文将围绕这些问题展开探讨。 跨国公司撤出的背景与
阅读更多...
认识、理解、分类——acm之搜索

认识、理解、分类——acm之搜索

普通搜索方法有两种：1、广度优先搜索；2、深度优先搜索； 更多搜索方法： 3、双向广度优先搜索； 4、启发式搜索（包括A*算法等）； 搜索通常会用到的知识点：状态压缩（位压缩，利用hash思想压缩）。
阅读更多...
【C++ Primer Plus习题】13.4

【C++ Primer Plus习题】13.4

大家好,这里是国中之林! ❥前些天发现了一个巨牛的人工智能学习网站，通俗易懂，风趣幽默，忍不住分享一下给大家。点击跳转到网站。有兴趣的可以点点进去看看← 问题: 解答: main.cpp #include <iostream>#include "port.h"int main() {Port p1;Port p2("Abc", "Bcc", 30);std::cout <<
阅读更多...
【C++】_list常用方法解析及模拟实现

【C++】_list常用方法解析及模拟实现

相信自己的力量，只要对自己始终保持信心，尽自己最大努力去完成任何事，就算事情最终结果是失败了，努力了也不留遗憾。💓💓💓 目录   ✨说在前面 🍋知识点一：什么是list？ •🌰1.list的定义 •🌰2.list的基本特性 •🌰3.常用接口介绍 🍋知识点二：list常用接口 •🌰1.默认成员函数 🔥构造函数（⭐） 🔥析构函数 •🌰2.list对象
阅读更多...
usaco 1.2 Transformations（模拟）

usaco 1.2 Transformations（模拟）

我的做法就是一个一个情况枚举出来 注意计算公式： （ 变换后的矩阵记为C） 顺时针旋转90°：C[i] [j]=A[n-j-1] [i] （旋转180°和270° 可以多转几个九十度来推） 对称：C[i] [n-j-1]=A[i] [j] 代码有点长 。。。 /*ID: who jayLANG: C++TASK: transform*/#include<
阅读更多...
客户案例：安全海外中继助力知名家电企业化解海外通邮困境

客户案例：安全海外中继助力知名家电企业化解海外通邮困境

1、客户背景 广东格兰仕集团有限公司（以下简称“格兰仕”），成立于1978年，是中国家电行业的领军企业之一。作为全球最大的微波炉生产基地，格兰仕拥有多项国际领先的家电制造技术，连续多年位列中国家电出口前列。格兰仕不仅注重业务的全球拓展，更重视业务流程的高效与顺畅，以确保在国际舞台上的竞争力。 2、需求痛点 随着格兰仕全球化战略的深入实施，其海外业务快速增长，电子邮件成为了关键的沟通工具。
阅读更多...
C++——stack、queue的实现及deque的介绍

C++——stack、queue的实现及deque的介绍

目录 1.stack与queue的实现 1.1stack的实现  1.2 queue的实现 2.重温vector、list、stack、queue的介绍 2.1 STL标准库中stack和queue的底层结构  3.deque的简单介绍 3.1为什么选择deque作为stack和queue的底层默认容器  3.2 STL中对stack与queue的模拟实现 ①stack模拟实现
阅读更多...
hdu4431麻将模拟

hdu4431麻将模拟

给13张牌。问增加哪些牌可以胡牌。 胡牌有以下几种情况： 1、一个对子 + 4组 3个相同的牌或者顺子。 2、7个不同的对子。 3、13幺 贪心的思想： 对于某张牌>=3个，先减去3个相同，再组合顺子。 import java.io.BufferedInputStream;import java.io.BufferedReader;import java.io.IOExcepti
阅读更多...
【每日一题】LeetCode 2181.合并零之间的节点（链表、模拟）

【每日一题】LeetCode 2181.合并零之间的节点（链表、模拟）

【每日一题】LeetCode 2181.合并零之间的节点（链表、模拟） 题目描述 给定一个链表，链表中的每个节点代表一个整数。链表中的整数由 0 分隔开，表示不同的区间。链表的开始和结束节点的值都为 0。任务是将每两个相邻的 0 之间的所有节点合并成一个节点，新节点的值为原区间内所有节点值的和。合并后，需要移除所有的 0，并返回修改后的链表头节点。 思路分析 初始化：创建一个虚拟头节点
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2