算法训练营训练并行处理（关联容器multiset）

关联容器：multiset

multiset是有序多重集合，允许多个值的键相同；使用时需要引入头文件#include 。
multiset的迭代器为双向访问，不支持随机访问。执行一次++和–操作的时间复杂度均为 O ( l o g n ) O(logn) O(logn)。

size/empty/clear：元素个数、判空、清空。begin/end：开始位置和结束位置。insert(x)：将元素x插入合集。erase(x)：删除所有等于x的元素。erase(it)：删除it迭代器指向的元素。find(x)：查找元素x在集合中的位置，若不存在，则返回end。count(x)：统计等于x的元素个数。
-lower_bound/upper_bound：返回大于等于x的最小元素位置、大于x的最小元素位置。 题目描述

并行处理中的编程范型之一是生产者/消费者范型，可以使用具有管理者进程和多个客户进程的系统来实现。客户可以是生产者、消费者等，管理者跟踪客户进程。每个进程都有一个成本（正整数，范围是1~10000）。具有相同成本的进程数不能超过10000。队列根据三种类型的请求进行管理。

a a a x x x：将成本为 x x x的进程添加到队列中。 r r r：根据当前管理者策略从队列中删除进程（如果可能） p p p i i i：执行管理者的策略 i i i，其中 i i i是1或2。1表示删除最小成本进程；2表示删除最大成本进程。默认管理者策略为1. e e e：结束请求列表。
只有在删除列表中包含已删除进程的序号时，管理者才会输出已删除进程的成本。编写一个程序来模拟管理者进程。

输入：输入中的每个数据集都有以下格式。

进程的最大成本删除列表的长度删除列表。查询已删除进程的序号列表；例如1 4，表示查询第1个和第4个已删除进程的成本。每个请求列表，各占一行
每个数据集都以 e e e请求结束。数据集以空行分隔。

输出：如果删除请求的序号在列表中，并且此时队列不为空，则单行输出删除的每个进程的成本。如果队列为空，则输出-1。以空行分隔不同数据集的结果。

算法设计

因为可能有多个相同成本，因此使用multiset解决。

用vis[]标记删除列表要显示的序号。默认管理者策略，p = 1。读入字符，判断执行相应的操作。进行删除操作时，如果队列为空，则输出-1；判断管理者策略，如果p = 1。则删除最小成本，否则删除最大成本。如果删除的成本序号在删除列表中，则输出该成本。

#include #include #include using namespace std;bool vis[10005];//相同成本进程数不能超过10000int k;//对已删除的进程统计计数multiset s;void del(int p);int main(){ char c; int m,n,x,p; while(~scanf("%d %d",&m,&n)){ memset(vis,false,sizeof(vis));//初始化布尔数组 s.clear();//清空multiset结构 for (int i = 0; i < n; ++i) { scanf("%d",&x); vis[x] = true; } p = 1; k = 1; while(scanf("%c",&c)){ if(c == 'e'){ break; } if(c == 'a'){ scanf("%d",&x); s.insert(x); } else if(c == 'p'){ scanf("%d",&x); p = x; } else if(c == 'r'){ del(p); } } printf("n"); } return 0;}void del(int p){ if(s.empty()){ printf("-1n"); return; } if(p == 1){//删除最小成本 if(vis[k++]){ printf("%dn",*s.begin());//迭代器就是广义指针，这里打印值，要对指针进行解引用 } s.erase(*s.begin());//删除操作 } else{//删除最大成本 if(vis[k++]){ printf("%dn",*s.rbegin());//反向迭代器，表示末尾元素 } s.erase(*s.rbegin()); }}

输入：

521 3a 2a 3ra 4p 2ra 5re

输出：

25