本文主要是介绍POJ 3481：双端队列 ← 数组模拟，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
【题目来源】
http://poj.org/problem?id=3481
【题目描述】
某银行的业务处理系统原理如下。
初始时，待处理业务队列（简称为队列）为空。
接下来，系统会收到一系列的请求，请求分为以下四种：
● 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 3481：http://poj.org/problem?id=3481
HDU 1908：http://acm.hdu.edu.cn/showproblem.php?pid=1908
AcWing 5125：https://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）】
#include<iostream>
#include<map>
using namespace std;map<int,int> mp;
map<int,int>::iterator it;
int K,P;
int cnt;int main() {int op;while(~scanf("%d",&op)) {if(op==0) break;if(op==1) {scanf("%d%d",&K,&P);mp[P]=K;cnt++;}if(op==2) {if(cnt==0) printf("0\n");else {it=mp.end();it--;printf("%d\n",it->second);mp.erase(it);cnt--;}}if(op==3) {if(cnt==0) printf("0\n");else {it=mp.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;map<int,int> mp;int main() {int K,P;int op;while(~scanf("%d",&op)) {if(op==0) break;if(op==2 && mp.size()==0) {printf("0\n");continue;}if(op==3 && mp.size()==0) {printf("0\n");continue;}if(op==1) {scanf("%d%d",&K,&P);mp[P]=K;continue;}if(op==2) {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 N=1E7+5;
struct Queue {int K;int P;
} q[N];int hh=0;
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(n==1) {scanf("%d %d",&a,&b);if(tt<hh) {q[hh].K=a;q[hh].P=b;tt=hh;} else {pos=tt+1;for(int i=hh; i<=tt; i++) {if(b<q[i].P) {pos=i;break;}}for(int j=tt; j>=pos; j--) {q[j+1].P=q[j].P;q[j+1].K=q[j].K;}q[pos].P=b;q[pos].K=a;tt++;}cnt++;} else if(n==3) {if(tt-hh>=0 && cnt) {printf("%d\n",q[hh].K);hh++;} else printf("0\n");if(cnt) cnt--;} else if(n==2) {if(tt-hh>=0 && cnt) {printf("%d\n",q[tt].K);q[tt].K=q[tt].P=0;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/8810139
https://blog.csdn.net/weixin_44226181/article/details/126758131
https://www.w3xue.com/exp/article/201811/6221.html
这篇关于POJ 3481：双端队列 ← 数组模拟的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
