训练2　并行处理

题目描述（POJ1281）：并行处理中的编程范型之一是生产者/消费者范型，可以用具有管理者进程和多个客户进程的系统来实现。客户可以是生产者、消费者等，管理者跟踪客户进程。每个进程都有成本（1～10 000的正整数）。具有相同成本的进程数量不能超过10 000。队列根据请求的类型进行管理，如下所述。

·　a x：将成本为x的进程添加到队列中。

·　r：根据当前管理者策略从队列中删除进程（若可能）。

·　p i：执行管理者策略i，其中i是1或2。1表示删除最小成本的进程；2表示删除最大成本的进程。默认的管理者策略为1。

·　e：结束请求列表。

只有删除的进程在删除列表中时，管理者才会输出该进程的成本。编写一个程序来模拟管理者进程。

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

·　进程的最大成本。

·　删除列表的长度。

·　删除列表，即待查询的删除进程列表。例如“1 4”表示查询第1个和第4个删除的进程的成本。

·　请求列表。每个请求列表各占一行。

每个数据集都以e请求结束。数据集以空行分隔。

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

1.算法设计

因为可能有多个相同的成本，所以可以用multiset解决。

（1）用vis［］数组标记删除列表要显示的序号。

（2）默认的管理者策略，p=1。

（3）读入字符，判断并执行相应的操作。

（4）进行删除操作时，若队列为空，则输出-1；否则判断管理者策略，若p=1，则删除最小成本的进程，否则删除最大成本的进程。若删除的进程在删除列表中，则输出该进程的成本。

2.算法实现