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];//相同成本进程数不能超过10000 int 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()); } }
输入：
5 2 1 3 a 2 a 3 r a 4 p 2 r a 5 r e
输出：
2 5
