设计网站公司长沙,软件外包公司主营业务,北京智能模板建站,wordpress会员网站【题目来源】http://poj.org/problem?id3481【题目描述】 某银行的业务处理系统原理如下。 初始时#xff0c;待处理业务队列#xff08;简称为队列#xff09;为空。 接下来#xff0c;系统会收到一系列的请求#xff0c;请求分为以下四种#xff1a; ● 0#xff0c;…【题目来源】http://poj.org/problem?id3481【题目描述】 某银行的业务处理系统原理如下。 初始时待处理业务队列简称为队列为空。 接下来系统会收到一系列的请求请求分为以下四种 ● 0表示系统需要停止服务。 ● 1 K P表示收到一个来自客户 K 的优先级为 P 的待处理业务并将该业务加入队列。 ● 2表示处理当前队列中优先级最高的待处理业务并将该业务从队列中删除。 ● 3表示处理当前队列中优先级最低的待处理业务并将该业务从队列中删除。 保证在任何时候当前队列中的现有待处理业务都满足不会有多个待处理业务来自同一客户也不会有多个待处理业务优先级相同。 也就是说在完成某客户的待处理业务之前不会再次收到该客户的待处理业务在完成某优先级的待处理业务之前不会再次收到该优先级的待处理业务。 给定银行系统收到的所有请求请你模拟系统处理过程。【输入格式】 输入若干行每行包含一个请求格式如题面描述。 数据保证有且仅有最后一行包含请求 0。【输出格式】 对于每个请求 2 和 3输出一行结果一个整数表示此次请求处理业务的客户编号。如果没有可处理业务则输出 0。【数据范围】 输入最多包含 10^6 个请求。 1≤K≤10^6, 1≤P≤10^7。【输入样例】 2 1 20 14 1 30 3 2 1 10 99 3 2 2 0【输出样例】 0 20 30 10 0【算法分析】 虽然本题来源于三个刷题网站 POJ 3481http://poj.org/problem?id3481HDU 1908http://acm.hdu.edu.cn/showproblem.php?pid1908 AcWing 5125https://www.acwing.com/problem/content/5128/ 但是下文使用数组模拟的代码仅在 POJ 3481 上通过而在 HDU 1908 及 AcWing 5125 上均超时。故可考虑使用 STL map 来实现经验证使用 STL map 实现的代码可在 POJ 3481、HDU 1908、AcWing 5125 上均通过。 大家学习时请优先使用下文中的【算法代码STL map 1】进行学习。若想学习切题的数组模拟法实现请参见本文最后一个代码【算法代码数组模拟】。【算法代码STL map 1】
#includeiostream
#includemap
using namespace std;mapint,int mp;
mapint,int::iterator it;
int K,P;
int cnt;int main() {int op;while(~scanf(%d,op)) {if(op0) break;if(op1) {scanf(%d%d,K,P);mp[P]K;cnt;}if(op2) {if(cnt0) printf(0\n);else {itmp.end();it--;printf(%d\n,it-second);mp.erase(it);cnt--;}}if(op3) {if(cnt0) printf(0\n);else {itmp.begin();printf(%d\n,it-second);mp.erase(it);cnt--;}}}return 0;
}/*
in:
2
1 20 14
1 30 3
2
1 10 99
3
2
2
0out:
0
20
30
10
0
*/
【算法代码STL map 2】
#include iostream
#include map
using namespace std;mapint,int mp;int main() {int K,P;int op;while(~scanf(%d,op)) {if(op0) break;if(op2 mp.size()0) {printf(0\n);continue;}if(op3 mp.size()0) {printf(0\n);continue;}if(op1) {scanf(%d%d,K,P);mp[P]K;continue;}if(op2) {printf(%d\n,(*mp.rbegin()).second);mp.erase(mp.find((*mp.rbegin()).first));} else {printf(%d\n,(*mp.begin()).second);mp.erase(mp.begin());}}return 0;
}/*
in:
2
1 20 14
1 30 3
2
1 10 99
3
2
2
0out:
0
20
30
10
0
*/
【算法代码数组模拟】
#include iostream
using namespace std;
const int N1E75;
struct Queue {int K;int P;
} q[N];int hh0;
int tt-1;
int cnt;
int pos; //Position of inserting into the queueint a,b;
int main() {int n;while(scanf(%d,n)!EOF,n) {if(n1) {scanf(%d %d,a,b);if(tthh) {q[hh].Ka;q[hh].Pb;tthh;} else {postt1;for(int ihh; itt; i) {if(bq[i].P) {posi;break;}}for(int jtt; jpos; j--) {q[j1].Pq[j].P;q[j1].Kq[j].K;}q[pos].Pb;q[pos].Ka;tt;}cnt;} else if(n3) {if(tt-hh0 cnt) {printf(%d\n,q[hh].K);hh;} else printf(0\n);if(cnt) cnt--;} else if(n2) {if(tt-hh0 cnt) {printf(%d\n,q[tt].K);q[tt].Kq[tt].P0;tt--;} else printf(0\n);if(cnt) cnt--;}}return 0;
}/*
in:
2
1 20 14
1 30 3
2
1 10 99
3
2
2
0out:
0
20
30
10
0
*/【参考文献】https://blog.csdn.net/spark_007/article/details/8810139https://blog.csdn.net/weixin_44226181/article/details/126758131https://www.w3xue.com/exp/article/201811/6221.html
