一 问题描述

银行的每个客户都有一个正整数标识 K，到银行请求服务时将收到一个正整数的优先级 P 。银行经理提议打破传统，在某些时候调用优先级最低的客户，而不是优先级最高的客户。系统将收到以下类型的请求：

① 0，系统需要停止服务。

② 1 K P，将客户 K 及优先级 P 添加到等待列表中。

③ 2，为优先级最高的客户提供服务，并将其从等待名单中删除。

④ 3，为优先级最低的客户提供服务，并将其从等待名单中删除。

二 输入

输入的每一行都包含一个请求，只有最后一行包含停止请求（代码0）。假设有请求在列表中包含新客户（代码1），在同一客户的列表中没有其他请求或有相同的优先级，标识符 K 总是小于10^6 ，优先级 P 总是小于10^7 。一个客户可以多次到银行请求服务，但是每次都获得不同的优先级。

三 输出

对代码为 2 或 3 的每个请求都单行输出所服务客户的标识。若请求在等待列表为空时到达，则输出 0。

四 输入和输出样例

1 输入样例

2

1 20 14

1 30 3

2

1 10 99

3

2

2

0

2 输出样例

0

20

30

10

0

五 分析和设计

本问题包括插入、删除优先级最高元素和删除优先级最低元素等 3 种操作，可以采用 Treap 解决。

六 代码

package com.platform.modules.alg.alglib.poj3481;

import java.util.Random;

public class Poj3481A {
    public String output = "";

    private int maxn = 100005;
    int n; // 结点数
    int cnt; // 结点存储下标累计
    int root; // 树根
    int maxval;
    int minval;
    private node tr[] = new node[maxn];

    public Poj3481A() {
        for (int i = 0; i < tr.length; i++) {
            tr[i] = new node();
        }
    }

    // 生成新结点
    int New(int val, int num) {
        tr[++cnt].val = val;
        tr[cnt].pri = Math.abs(new Random().nextInt()) % 100;
        tr[cnt].num = num;
        tr[cnt].rc = tr[cnt].lc = 0;
        return cnt;
    }

    // 右旋
    int zig(int p) {
        int q = tr[p].lc;
        tr[p].lc = tr[q].rc;
        tr[q].rc = p;
        // 现在 q 为根
        p = q;
        return p;
    }

    // 左旋
    int zag(int p) {
        int q = tr[p].rc;
        tr[p].rc = tr[q].lc;
        tr[q].lc = p;
        // 现在 q 为根
        p = q;
        return p;
    }

    // 在 p 的子树插入值 val
    int Insert(int p, int val, int num) {
        if (p == 0) {
            p = New(val, num);
            return p;
        }
        if (val <= tr[p].val) {
            tr[p].lc = Insert(tr[p].lc, val, num);
            if (tr[p].pri < tr[tr[p].lc].pri)
                p = zig(p);
        } else {
            tr[p].rc = Insert(tr[p].rc, val, num);
            if (tr[p].pri < tr[tr[p].rc].pri)
                p = zag(p);
        }
        return p;
    }

    // 在 p 的子树删除值val
    int Delete(int p, int val) {
        if (p == 0)
            return p;
        if (val == tr[p].val) {
            if (tr[p].lc == 0 || tr[p].rc == 0)
                p = tr[p].lc + tr[p].rc; // 有一个儿子为空，直接用儿子代替
            else if (tr[tr[p].lc].pri > tr[tr[p].rc].pri) {
                p = zig(p);
                tr[p].rc = Delete(tr[p].rc, val);
            } else {
                p = zag(p);
                tr[p].lc = Delete(tr[p].lc, val);
            }
            return p;
        }
        if (val < tr[p].val)
            tr[p].lc = Delete(tr[p].lc, val);
        else
            tr[p].rc = Delete(tr[p].rc, val);
        return p;
    }

    // 找优先级最大的结点编号
    void printmax(int p) {
        while (tr[p].rc > 0) {
            p = tr[p].rc;
        }
        output += tr[p].num + "\n";
        maxval = tr[p].val;
    }

    // 找优先级最低的结点编号
    void printmin(int p) {
        while (tr[p].lc > 0) {
            p = tr[p].lc;
        }
        output += tr[p].num + "\n";
        minval = tr[p].val;
    }

    public String cal(String input) {
        int num, val;
        String[] line = input.split("\n");
        int count = 0;
        while (true) {
            String commad[] = line[count++].split(" ");
            n = Integer.parseInt(commad[0]);
            switch (n) {
                case 0:
                    return output;
                case 1:
                    num = Integer.parseInt(commad[1]);
                    val = Integer.parseInt(commad[2]);
                    root = Insert(root, val, num);
                    break;
                case 2:
                    if (root == 0)
                        output += "0" + "\n";
                    else {
                        printmax(root);
                        root = Delete(root, maxval);
                    }
                    break;
                case 3:
                    if (root == 0)
                        output += "0" + "\n";
                    else {
                        printmin(root);
                        root = Delete(root, minval);
                    }
                    break;
            }
        }
    }
}

class node {
    int lc, rc; // 左右孩子
    int val, pri; // 值，优先级
    int num; // 重复个数
}

七 测试