一 问题描述

并行处理中的编程规范之一是生产者/消费者范型，可以使用具有管理者进程和多个客户端进程的系统来实现。客户可以是生产者、消费者等。管理者跟踪客户进程。每个进程都有一个成本，允许具有相同成本的进程。队列根据三种类型的请求进行管理。

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

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

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

e：结束请求列表。

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

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

进程的最大成本。

删除列表的长度。

删除列表。查询已删除进行的序号列表：例如 1 4，表示查询第 1 个和第 4 个已删除进程的成本。

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

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

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

输入样例：
5

2

1 3

a 2

a 3

r

a 4

p 2

r

a 5

r

e

输出样例

2

5

二 算法设计

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

1 用 vis[] 标记删除列表要显示的序号。

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

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

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

三 实现

package multiset;

import com.google.common.collect.HashMultiset;
import com.google.common.collect.Multiset;

import java.util.Iterator;
import java.util.Scanner;

public class MultiSetTest {
    private static boolean[] vis = new boolean[100];
    static Multiset<Integer> s = HashMultiset.create();
    // 要删除进程的序号
    private static int k;

    public static void del(int p) {
        if (s.isEmpty()) {
            System.out.println("-1");
            return;
        }
        Iterator<Integer> iterator = s.iterator();
        Integer point = null;
        if (p == 1) {
            if (iterator.hasNext()) {
                // 定位到第1个
                point = iterator.next();
                if (vis[k++]) {
                    System.out.println(point);
                }
            }
            s.remove(point);
        } else {
            while (iterator.hasNext()) {
                // 定位到最后一个
                point = iterator.next();
            }
            if (vis[k++]) {
                System.out.println(point);
            }
            s.remove(point);
        }
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        String c;
        // 进程的最大成本
        int m = scanner.nextInt();
        // 删除列表的长度
        int n = scanner.nextInt();
        for (int i = 0; i < n; i++) {
            // 要删除的序号
            int x = scanner.nextInt();
            vis[x] = true;
        }
        // 删除策略
        int p = 1;
        k = 1;
        while (true) {
            c = scanner.next();
            if (c.equals("e")) {
                break;
            } else if (c.equals("a")) {
                int x = scanner.nextInt();
                s.add(x);
            } else if (c.equals("p")) {
                p = scanner.nextInt();
            } else if (c.equals("r")) {
                del(p);
            }
        }
    }
}

四 测试

绿色为输入，白色为输出。