(A卷,100分)- 插队（Java & JS & Python）

题目描述

某银行将客户分为了若干个优先级， 1 级最高， 5 级最低，当你需要在银行办理业务时，优先级高的人随时可以插队到优先级低的人的前面。

现在给出一个人员到来和银行办理业务的时间序列，请你在每次银行办理业务时输出客户的编号。

如果同时有多位优先级相同且最高的客户，则按照先来后到的顺序办理。

输入描述

输入第一行是一个正整数 n ,表示输入的序列中的事件数量。(1 ≤ n ≤ 500)

接下来有 n 行，每行第一个字符为 a 或 p 。

当字符为 a 时，后面会有两个的正整数 num 和 x ,表示到来的客户编号为 num ,优先级为 x ;

当字符为 p 时，表示当前优先级最高的客户去办理业务。

输出描述

输出包含若干行，对于每个 p ， 输出一行，仅包含一个正整数 num , 表示办理业务的客户编号。

用例

题目解析

简单的优先队列应用。

但是本题需要注意几个问题：

1、客户编号应该不是先来后到的顺序，输入顺序才是

2、会不会存在p数量超过a数量的情况？我这边考虑了这种情况，如果p时，优先队列已经没有客户了，那么就输出空

JavaScript算法源码

JS没有内置的优先队列实现，考试时若时间不够可以考虑使用有序数组代码。

优先队列实现，请看：

/* JavaScript Node ACM模式 控制台输入获取 */
const readline = require("readline");

const rl = readline.createInterface({
  input: process.stdin,
  output: process.stdout,
});

const lines = [];
let n;
rl.on("line", (line) => {
  lines.push(line);

  if (lines.length === 1) {
    n = lines[0] - 0;
  }

  if (n && lines.length === n + 1) {
    lines.shift();
    const seq = lines.map((line) => line.split(" "));
    getResult(n, seq);
    lines.length = 0;
  }
});

function getResult(n, seq) {
  const pq = new PriorityQueue((a, b) =>
    a[0] != b[0] ? a[0] - b[0] : a[1] - b[1]
  );

  for (let i = 0; i < n; i++) {
    const tmp = seq[i];

    switch (tmp[0]) {
      case "a":
        const num = Number(tmp[1]);
        const x = Number(tmp[2]);
        pq.offer([x, i, num]);
        break;
      case "p":
        const cust = pq.poll();
        if (cust) console.log(cust[2]);
        else console.log("");
    }
  }
}

// 基于堆实现优先队列
class PriorityQueue {
  constructor(cpr) {
    this.queue = [];
    this.cpr = cpr;
  }

  swap(a, b) {
    const tmp = this.queue[a];
    this.queue[a] = this.queue[b];
    this.queue[b] = tmp;
  }

  // 上浮
  swim() {
    let c = this.queue.length - 1;

    while (c >= 1) {
      const f = Math.floor((c - 1) / 2);

      if (this.cpr(this.queue[c], this.queue[f]) < 0) {
        this.swap(c, f);
        c = f;
      } else {
        break;
      }
    }
  }

  // 入队
  offer(val) {
    this.queue.push(val);
    this.swim();
  }

  // 下沉
  sink() {
    let f = 0;

    while (true) {
      let c1 = 2 * f + 1;
      let c2 = c1 + 1;

      let c;
      let val1 = this.queue[c1];
      let val2 = this.queue[c2];
      if (val1 && val2) {
        c = this.cpr(val1, val2) < 0 ? c1 : c2;
      } else if (val1 && !val2) {
        c = c1;
      } else if (!val1 && val2) {
        c = c2;
      } else {
        break;
      }

      if (this.cpr(this.queue[c], this.queue[f]) < 0) {
        this.swap(c, f);
        f = c;
      } else {
        break;
      }
    }
  }

  // 出队
  poll() {
    this.swap(0, this.queue.length - 1);
    const res = this.queue.pop();
    this.sink();
    return res;
  }

  peek() {
    return this.queue[0];
  }

  size() {
    return this.queue.length;
  }
}

Java算法源码

import java.util.PriorityQueue;
import java.util.Scanner;

public class Main {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);

    int n = Integer.parseInt(sc.nextLine());

    String[][] arr = new String[n][];
    for (int i = 0; i < n; i++) {
      arr[i] = sc.nextLine().split(" ");
    }

    getResult(n, arr);
  }

  public static void getResult(int n, String[][] arr) {
    PriorityQueue<int[]> pq =
        new PriorityQueue<>((a, b) -> a[0] != b[0] ? a[0] - b[0] : a[1] - b[1]);

    for (int i = 0; i < n; i++) {
      String[] tmp = arr[i];
      switch (tmp[0]) {
        case "a":
          int num = Integer.parseInt(tmp[1]);
          int x = Integer.parseInt(tmp[2]);
          pq.offer(new int[] {x, i, num}); // i 是先来后到的顺序
          break;
        case "p":
          int[] poll = pq.poll();
          if (poll != null) System.out.println(poll[2]);
          else System.out.println("");
      }
    }
  }
}

Python算法源码

import queue

# 输入获取
n = int(input())
seq = [input().split() for _ in range(n)]


# 定义一个客户类，实现自定义优先级
class Customer:
    def __init__(self, num, x, index):
        """
        :param num: 客户编号
        :param x: 客户优先级
        :param index: 客户先来后到顺序
        """
        self.num = num
        self.x = x
        self.index = index

    def __lt__(self, other):
        if self.x != other.x:
            return self.x < other.x
        else:
            return self.index < other.index


# 算法入口
def getResult(n, seq):
    pq = queue.PriorityQueue()

    for i in range(n):
        tmp = seq[i]

        if tmp[0] == 'a':
            num = int(tmp[1])
            x = int(tmp[2])
            pq.put(Customer(num, x, i))
        elif tmp[0] == 'p':
            if pq.qsize() > 0:
                customer = pq.get()
                print(customer.num)
            else:
                print("")


# 算法调用
getResult(n, seq)