【排序】银行插队（许老师题解）

题目描述与示例

本题练习地址：https://www.algomooc.com/problem/P2565

题目描述

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

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

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

输入描述

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

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

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

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

输出描述

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

补充说明

示例一

输入

输出

示例二

输入

输出

2
5

解题思路

显然这是一道动态排序的题目。

普通排序模拟

由于数据量较小，我们可以用普通的排序方法。

首先我们构建整体的代码框架，对于每一行输入，我们首先需要判断第一个字符是"a"还是"p"。

如果是"a"，则这个客户需要进入排队
如果是"p"，则需要进行业务办理，令优先级最高的人进行业务办理

故整体代码框架如下

for t in range(n):
    row = input()
    if row[0] == "a":
        pass
    elif row[0] == "p":
        pass

接下来讨论遇到"a"和"p"分别需要进行什么处理。

遇到"a"，则这个客户需要进入排队。我们可以把该客户的编号和优先级，储存在一起。

有因为当遇见优先级相等的时候，我们还需要按照先来后到顺序来排序，所以还需要该客户出现的时刻t。

优先级，出现时刻，编号构成一个三元组储存在全局的数组lst中。即

# 循环n次，输入n行，注意必须体现时刻t
for t in range(n):
    # 输入当前行
    row = input()
    # 如果该行第一个字符是"a"，则储存客户信息
    if row[0] == "a":
        op, num, x = row.split()
        lst.append((int(x), t, int(num)))
    # 如果该行第一个字符是"p"，则进行业务办理
	pass

遇到"p"，则需要进行业务办理，令优先级最高的人进行业务办理。

由于业务办理完毕后，我们需要删除这个人，所以我们将优先级最高的人排序在数组lst最末尾并弹出。

排序的lambda函数如下。

lst.sort(key = lambda item: (item[0], item[1]), reverse = True)

其中item[0]表示先按照优先级升序排序（小的数字优先级更高），item[1]表示在同一优先级出现时按照先来后到的时间顺序升序排序。再取反转，就能够使得优先级最高的客户排在lst的末尾了。

再将lst的末尾元素弹出，取该三元组索引2的内容得到这个客户的编号，储存在ans中。

故整体代码如下

lst = list()
ans = list()

# 循环n次，输入n行，注意必须体现时刻t
for t in range(n):
    # 输入当前行
    row = input()
    # 如果该行第一个字符是"a"，则储存客户信息
    if row[0] == "a":
        op, num, x = row.split()
        lst.append((int(x), t, int(num)))
    # 如果该行第一个字符是"p"，则进行业务办理
    elif row[0] == "p":
        lst.sort(key = lambda item: (item[0], item[1]), reverse = True)
        ans.append(lst.pop()[2])

这样代码基本就写完了。

*堆/优先队列模拟

对于这种动态排序的问题，我们还可以思考使用堆/优先队列来优化这个模拟过程。

本做法不做强制要求，学有余力的同学可以自行学习掌握。

注意到反复的排序其实非常浪费时间，我们可以构建一个堆heap来维护这个过程。

对于遇到"a"的情况，我们需要将三元组(int(x), t, int(num))储存入数组lst改为储存入堆heap中。

Python默认的堆操作是最小堆，而优先级int(x)和时刻t都是以小的值的具有更高优先级。即

heappush(heap, (int(x), t, int(num)))

遇到"p"的情况则更加简单，直接令堆顶元素出堆，就是我们想要的具有最高优先级的元素。即

item = heappop(heap)
ans.append(item[2])

故整体代码为

# 构建储存客户信息的优先队列heap
heap = list()
# 构建答案列表ans
ans = list()

# 循环n次，输入n行，注意必须体现时刻t
for t in range(n):
    # 输入当前行
    row = input()
    # 如果该行第一个字符是"a"，则储存客户信息
    if row[0] == "a":
        op, num, x = row.split()
        heappush(heap, (int(x), t, int(num)))
    # 如果该行第一个字符是"p"，则进行业务办理
    elif row[0] == "p":
        item = heappop(heap)
        ans.append(item[2])

代码

解法一（普通排序+lambda匿名函数）

Python

# 题目：【排序】银行插队
# 分值：100
# 作者：许老师-闭着眼睛学数理化
# 算法：模拟，排序
# 代码看不懂的地方，请直接在群上提问


# 输入接下来输入的行数
n = int(input())

# 构建储存客户信息的数组lst
lst = list()
# 构建答案列表ans
ans = list()

# 循环n次，输入n行，注意必须体现时刻t
for t in range(n):
    # 输入当前行
    row = input()
    # 如果该行第一个字符是"a"，则储存客户信息
    if row[0] == "a":
        op, num, x = row.split()
        lst.append((int(x), t, int(num)))
    # 如果该行第一个字符是"p"，则进行业务办理
    elif row[0] == "p":
        lst.sort(key = lambda item: (item[0], item[1]), reverse = True)
        ans.append(lst.pop()[2])

# 逐行输出结果
for num in ans:
    print(num)

Java

import java.util.*;

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

        // 输入接下来输入的行数
        int n = Integer.parseInt(scanner.nextLine());

        // 构建储存客户信息的队列lst
        List<Customer> lst = new ArrayList<>();
        // 构建答案列表ans
        List<Integer> ans = new ArrayList<>();

        // 循环n次，输入n行，注意必须体现时刻t
        for (int t = 0; t < n; t++) {
            // 输入当前行
            String row = scanner.nextLine();

            // 如果该行第一个字符是"a"，则储存客户信息
            if (row.startsWith("a")) {
                String[] parts = row.split(" ");
                int num = Integer.parseInt(parts[1]);
                int x = Integer.parseInt(parts[2]);
                lst.add(new Customer(x, t, num));
            }
            // 如果该行第一个字符是"p"，则进行业务办理
            else if (row.startsWith("p")) {
                // 按优先级降序排序
                lst.sort((c1, c2) -> {
                    if (c2.priority != c1.priority) {
                        return Integer.compare(c2.priority, c1.priority);
                    }
                    // 按照到达时间降序排序
                    return Integer.compare(c2.time, c1.time);
                });
                // 将优先级最高的客户加入答案，并移除
                ans.add(lst.remove(lst.size() - 1).id);
            }
        }

        // 逐行输出结果
        for (int num : ans) {
            System.out.println(num);
        }
    }

    // 客户类
    static class Customer {
        int priority; // 优先级
        int time;     // 到达时间
        int id;       // 客户编号

        public Customer(int priority, int time, int id) {
            this.priority = priority;
            this.time = time;
            this.id = id;
        }
    }
}

C++

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;

// 客户类
class Customer {
public:
    int priority; // 优先级
    int time;     // 到达时间
    int id;       // 客户编号

    // 构造函数
    Customer(int priority, int time, int id) : priority(priority), time(time), id(id) {}

    // 重载小于运算符，按照优先级降序和到达时间降序排序
    bool operator<(const Customer& other) const {
        if (this->priority != other.priority) {
            return this->priority > other.priority;
        }
        return this->time > other.time;
    }
};

int main() {
    int n;
    cin >> n;  // 输入接下来输入的行数
    cin.ignore(); // 忽略换行符

    // 构建储存客户信息的队列lst
    vector<Customer> lst;
    // 构建答案列表ans
    vector<int> ans;

    // 循环n次，输入n行，注意必须体现时刻t
    for (int t = 0; t < n; t++) {
        string row;
        getline(cin, row);

        // 如果该行第一个字符是"a"，则储存客户信息
        if (row[0] == 'a') {
            int num, x;
            sscanf(row.c_str(), "a %d %d", &num, &x);
            lst.push_back(Customer(x, t, num));
        }
        // 如果该行第一个字符是"p"，则进行业务办理
        else if (row[0] == 'p') {
            // 按优先级排序
            sort(lst.begin(), lst.end());
            // 将优先级最高的客户加入答案，并移除
            ans.push_back(lst.back().id);
            lst.pop_back();
        }
    }

    // 逐行输出结果
    for (int num : ans) {
        cout << num << endl;
    }

    return 0;
}

C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

// 客户类
typedef struct {
    int priority; // 优先级
    int time;     // 到达时间
    int id;       // 客户编号
} Customer;

// 按优先级排序的比较函数
int compare(const void* a, const void* b) {
    Customer* c1 = (Customer*)a;
    Customer* c2 = (Customer*)b;
    if (c1->priority != c2->priority) {
        return c2->priority - c1->priority; // 优先级降序
    }
    return c2->time - c1->time; // 到达时间降序
}

int main() {
    int n;
    scanf("%d\n", &n);  // 输入接下来输入的行数

    // 构建储存客户信息的数组
    Customer lst[1000];  // 假设最大客户数为1000
    int lstSize = 0;  // 客户队列大小
    int ans[1000];  // 答案数组
    int ansSize = 0;  // 答案大小

    // 循环n次，输入n行，注意必须体现时刻t
    for (int t = 0; t < n; t++) {
        char row[100];
        fgets(row, sizeof(row), stdin);

        // 如果该行第一个字符是"a"，则储存客户信息
        if (row[0] == 'a') {
            int num, x;
            sscanf(row, "a %d %d", &num, &x);
            lst[lstSize].priority = x;
            lst[lstSize].time = t;
            lst[lstSize].id = num;
            lstSize++;
        }
        // 如果该行第一个字符是"p"，则进行业务办理
        else if (row[0] == 'p') {
            // 按优先级排序
            qsort(lst, lstSize, sizeof(Customer), compare);
            // 将优先级最高的客户加入答案，并移除
            ans[ansSize++] = lst[lstSize - 1].id;
            lstSize--;
        }
    }

    // 逐行输出结果
    for (int i = 0; i < ansSize; i++) {
        printf("%d\n", ans[i]);
    }

    return 0;
}

Node JavaScript

const readline = require("readline");

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

let inputLines = [];
rl.on("line", (line) => {
    inputLines.push(line);
}).on("close", () => {
    // 输入接下来输入的行数
    const n = parseInt(inputLines[0]);

    // 构建储存客户信息的队列lst
    const lst = [];
    // 构建答案列表ans
    const ans = [];

    // 循环n次，输入n行，注意必须体现时刻t
    for (let t = 1; t <= n; t++) {
        const row = inputLines[t];

        // 如果该行第一个字符是"a"，则储存客户信息
        if (row.startsWith("a")) {
            const [_, num, x] = row.split(" ").map(Number);
            lst.push({ priority: x, time: t - 1, id: num });
        }
        // 如果该行第一个字符是"p"，则进行业务办理
        else if (row.startsWith("p")) {
            // 按优先级降序排序
            lst.sort((c1, c2) => {
                if (c2.priority !== c1.priority) {
                    return c2.priority - c1.priority;
                }
                // 按照到达时间降序排序
                return c2.time - c1.time;
            });
            // 将优先级最高的客户加入答案，并移除
            ans.push(lst.pop().id);
        }
    }

    // 逐行输出结果
    ans.forEach((num) => console.log(num));
});

Go

package main

import (
        "bufio"
        "fmt"
        "os"
        "sort"
        "strconv"
        "strings"
)

// 客户结构体
type Customer struct {
        priority int // 优先级
        time     int // 到达时间
        id       int // 客户编号
}

func main() {
        scanner := bufio.NewScanner(os.Stdin)
        scanner.Scan()
        // 输入接下来输入的行数
        n, _ := strconv.Atoi(scanner.Text())

        // 构建储存客户信息的切片lst
        var lst []Customer
        // 构建答案列表ans
        var ans []int

        // 循环n次，输入n行，注意必须体现时刻t
        for t := 0; t < n; t++ {
                scanner.Scan()
                row := scanner.Text()

                // 如果该行第一个字符是"a"，则储存客户信息
                if strings.HasPrefix(row, "a") {
                        parts := strings.Split(row, " ")
                        num, _ := strconv.Atoi(parts[1])
                        x, _ := strconv.Atoi(parts[2])
                        lst = append(lst, Customer{priority: x, time: t, id: num})
                } else if strings.HasPrefix(row, "p") {
                        // 按优先级降序排序
                        sort.Slice(lst, func(i, j int) bool {
                                if lst[i].priority != lst[j].priority {
                                        return lst[i].priority > lst[j].priority
                                }
                                // 按到达时间降序排序
                                return lst[i].time > lst[j].time
                        })
                        // 将优先级最高的客户加入答案，并移除
                        ans = append(ans, lst[len(lst)-1].id)
                        lst = lst[:len(lst)-1]
                }
        }

        // 逐行输出结果
        for _, num := range ans {
                fmt.Println(num)
        }
}

时空复杂度

时间复杂度：O(K+MKlogK)。M为调用"p"的次数，K为客户总人数，单次排序所花费的时间复杂度为O(KlogK)，M次排序共花费O(MKlogK)。另外还存在K次输入客户信息。

空间复杂度：O(K)。lst数组所占空间。

解法二（堆/优先队列维护动态排序）

Python

# 题目：【排序】银行插队
# 分值：100
# 作者：许老师-闭着眼睛学数理化
# 算法：模拟，排序，优先队列
# 代码看不懂的地方，请直接在群上提问

from heapq import heappop, heappush


# 输入接下来输入的行数
n = int(input())

# 构建储存客户信息的优先队列heap
heap = list()
# 构建答案列表ans
ans = list()

# 循环n次，输入n行，注意必须体现时刻t
for t in range(n):
    # 输入当前行
    row = input()
    # 如果该行第一个字符是"a"，则储存客户信息
    if row[0] == "a":
        op, num, x = row.split()
        heappush(heap, (int(x), t, int(num)))
    # 如果该行第一个字符是"p"，则进行业务办理
    elif row[0] == "p":
        item = heappop(heap)
        ans.append(item[2])

# 逐行输出结果
for num in ans:
    print(num)

Java

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

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

        // 输入接下来输入的行数
        int n = Integer.parseInt(scanner.nextLine());

        // 构建储存客户信息的优先队列heap
        PriorityQueue<Customer> heap = new PriorityQueue<>();
        // 构建答案列表ans
        StringBuilder ans = new StringBuilder();

        // 循环n次，输入n行，注意必须体现时刻t
        for (int t = 0; t < n; t++) {
            // 输入当前行
            String row = scanner.nextLine();
            // 如果该行第一个字符是"a"，则储存客户信息
            if (row.startsWith("a")) {
                String[] parts = row.split(" ");
                int num = Integer.parseInt(parts[1]);
                int x = Integer.parseInt(parts[2]);
                heap.offer(new Customer(x, t, num));
            }
            // 如果该行第一个字符是"p"，则进行业务办理
            else if (row.startsWith("p")) {
                Customer item = heap.poll();
                ans.append(item.num).append("\n");
            }
        }

        // 输出答案
        System.out.print(ans.toString());
    }

    // 客户类实现Comparable接口，用于自定义优先级规则
    static class Customer implements Comparable<Customer> {
        int priority; // 优先级
        int time;     // 到达时间
        int num;      // 客户编号

        public Customer(int priority, int time, int num) {
            this.priority = priority;
            this.time = time;
            this.num = num;
        }

        @Override
        public int compareTo(Customer other) {
            if (this.priority != other.priority) {
                return Integer.compare(this.priority, other.priority); // 优先级升序
            }
            return Integer.compare(this.time, other.time); // 到达时间升序
        }
    }
}

C++

#include <iostream>
#include <queue>
#include <vector>
#include <tuple>
#include <string>

using namespace std;

struct Customer {
    int priority; // 优先级
    int time;     // 到达时间
    int num;      // 客户编号

    // 重载<，实现最小堆
    bool operator<(const Customer& other) const {
        if (priority != other.priority) {
            return priority > other.priority; // 优先级升序
        }
        return time > other.time; // 到达时间升序
    }
};

int main() {
    int n;
    cin >> n;
    cin.ignore();

    // 构建储存客户信息的优先队列heap
    priority_queue<Customer> heap;
    // 构建答案列表ans
    vector<int> ans;

    // 循环n次，输入n行，注意必须体现时刻t
    for (int t = 0; t < n; t++) {
        string row;
        getline(cin, row);

        // 如果该行第一个字符是"a"，则储存客户信息
        if (row[0] == 'a') {
            int num, x;
            sscanf(row.c_str(), "a %d %d", &num, &x);
            heap.push({x, t, num});
        }
        // 如果该行第一个字符是"p"，则进行业务办理
        else if (row[0] == 'p') {
            Customer item = heap.top();
            heap.pop();
            ans.push_back(item.num);
        }
    }

    // 输出答案
    for (int num : ans) {
        cout << num << endl;
    }

    return 0;
}

C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

// 定义客户结构体
typedef struct {
    int priority;  // 优先级
    int time;      // 到达时间
    int id;        // 客户编号
} Customer;

// c语言里没有优先队列这个数据结构，需要自己构建
// 定义最小堆结构体
typedef struct {
    Customer *data; // 存储客户的数组
    int size;       // 当前堆大小
    int capacity;   // 堆容量
} MinHeap;

// 初始化堆
MinHeap *initHeap(int capacity) {
    MinHeap *heap = (MinHeap *)malloc(sizeof(MinHeap));
    heap->data = (Customer *)malloc(capacity * sizeof(Customer));
    heap->size = 0;
    heap->capacity = capacity;
    return heap;
}

// 交换两个客户
void swap(Customer *a, Customer *b) {
    Customer temp = *a;
    *a = *b;
    *b = temp;
}

// 向堆中插入元素
void heapPush(MinHeap *heap, Customer value) {
    if (heap->size == heap->capacity) {
        printf("Heap is full!\n");
        return;
    }
    heap->data[heap->size] = value;
    int i = heap->size;
    heap->size++;

    // 上浮操作
    while (i > 0) {
        int parent = (i - 1) / 2;
        if (heap->data[i].priority < heap->data[parent].priority ||
            (heap->data[i].priority == heap->data[parent].priority && heap->data[i].time < heap->data[parent].time)) {
            swap(&heap->data[i], &heap->data[parent]);
            i = parent;
        } else {
            break;
        }
    }
}

// 从堆中弹出最小元素
Customer heapPop(MinHeap *heap) {
    if (heap->size == 0) {
        printf("Heap is empty!\n");
        exit(1);
    }
    Customer minValue = heap->data[0];
    heap->data[0] = heap->data[heap->size - 1];
    heap->size--;

    // 下沉操作
    int i = 0;
    while (i * 2 + 1 < heap->size) {
        int left = i * 2 + 1;
        int right = i * 2 + 2;
        int smallest = i;

        if (heap->data[left].priority < heap->data[smallest].priority ||
            (heap->data[left].priority == heap->data[smallest].priority && heap->data[left].time < heap->data[smallest].time)) {
            smallest = left;
        }
        if (right < heap->size && (heap->data[right].priority < heap->data[smallest].priority ||
            (heap->data[right].priority == heap->data[smallest].priority && heap->data[right].time < heap->data[smallest].time))) {
            smallest = right;
        }
        if (smallest == i) {
            break;
        }
        swap(&heap->data[i], &heap->data[smallest]);
        i = smallest;
    }
    return minValue;
}

// 释放堆内存
void freeHeap(MinHeap *heap) {
    free(heap->data);
    free(heap);
}

int main() {
    int n;
    scanf("%d", &n);

    // 初始化最小堆
    MinHeap *heap = initHeap(n);

    // 存储答案
    int ans[n];
    int ansSize = 0;

    // 循环处理输入
    for (int t = 0; t < n; t++) {
        char op[10];
        scanf("%s", op);

        if (op[0] == 'a') {
            int num, x;
            scanf("%d %d", &num, &x);
            Customer customer = {x, t, num};
            heapPush(heap, customer);
        } else if (op[0] == 'p') {
            Customer customer = heapPop(heap);
            ans[ansSize++] = customer.id;
        }
    }

    // 输出结果
    for (int i = 0; i < ansSize; i++) {
        printf("%d\n", ans[i]);
    }

    // 释放堆内存
    freeHeap(heap);
    return 0;
}

Node JavaScript

const readline = require('readline');

// 创建输入接口
const rl = readline.createInterface({
    input: process.stdin,
    output: process.stdout,
});

// 构建储存客户信息的优先队列
const heap = [];
// 构建答案列表
const ans = [];

// js里没有优先队列这个数据结构，需要自己构建
// 最小堆插入函数
function heappush(heap, item) {
    heap.push(item);
    let i = heap.length - 1;
    while (i > 0) {
        const parent = Math.floor((i - 1) / 2);
        if (heap[parent][0] < heap[i][0] || 
            (heap[parent][0] === heap[i][0] && heap[parent][1] <= heap[i][1])) {
            break;
        }
        [heap[parent], heap[i]] = [heap[i], heap[parent]];
        i = parent;
    }
}

// 最小堆弹出函数
function heappop(heap) {
    if (heap.length === 1) return heap.pop();
    const top = heap[0];
    heap[0] = heap.pop();
    let i = 0;
    while (true) {
        let left = 2 * i + 1;
        let right = 2 * i + 2;
        let smallest = i;

        if (left < heap.length && (heap[left][0] < heap[smallest][0] || 
            (heap[left][0] === heap[smallest][0] && heap[left][1] < heap[smallest][1]))) {
            smallest = left;
        }

        if (right < heap.length && (heap[right][0] < heap[smallest][0] || 
            (heap[right][0] === heap[smallest][0] && heap[right][1] < heap[smallest][1]))) {
            smallest = right;
        }

        if (smallest === i) break;
        [heap[i], heap[smallest]] = [heap[smallest], heap[i]];
        i = smallest;
    }
    return top;
}

let n = 0;
let t = 0;

// 处理输入
rl.on('line', (line) => {
    if (n === 0) {
        n = parseInt(line);
    } else {
        if (line[0] === 'a') {
            const [op, num, x] = line.split(' ');
            heappush(heap, [parseInt(x), t, parseInt(num)]);
            t++;
        } else if (line[0] === 'p') {
            const item = heappop(heap);
            ans.push(item[2]);
        }
    }

    if (ans.length === n) {
        rl.close();
    }
});

// 输出结果
rl.on('close', () => {
    for (const num of ans) {
        console.log(num);
    }
});

Go

package main

import (
        "container/heap"
        "fmt"
)

// Customer 定义客户结构体
type Customer struct {
        priority int // 优先级
        time     int // 到达时间
        id       int // 客户编号
}

// PriorityQueue 实现最小堆结构，存储 Customer
type PriorityQueue []*Customer

// Len 返回队列长度
func (pq PriorityQueue) Len() int {
        return len(pq)
}

// Less 定义优先级比较规则
// 优先级越小越优先；如果优先级相同，按时间先后排序
func (pq PriorityQueue) Less(i, j int) bool {
        if pq[i].priority != pq[j].priority {
                return pq[i].priority < pq[j].priority
        }
        return pq[i].time < pq[j].time
}

// Swap 交换两个元素
func (pq PriorityQueue) Swap(i, j int) {
        pq[i], pq[j] = pq[j], pq[i]
}

// Push 向堆中插入元素
func (pq *PriorityQueue) Push(x interface{}) {
        *pq = append(*pq, x.(*Customer))
}

// Pop 从堆中弹出最小元素
func (pq *PriorityQueue) Pop() interface{} {
        old := *pq
        n := len(old)
        item := old[n-1]
        *pq = old[:n-1]
        return item
}

func main() {
        var n int
        fmt.Scan(&n)

        // 初始化优先队列
        pq := &PriorityQueue{}
        heap.Init(pq)

        // 存储答案
        var ans []int

        // 循环处理输入
        for t := 0; t < n; t++ {
                var op string
                fmt.Scan(&op)

                if op == "a" {
                        // 处理 "a" 操作，添加客户信息
                        var num, x int
                        fmt.Scan(&num, &x)
                        customer := &Customer{
                                priority: x,
                                time:     t,
                                id:       num,
                        }
                        heap.Push(pq, customer)
                } else if op == "p" {
                        // 处理 "p" 操作，弹出最小优先级的客户
                        customer := heap.Pop(pq).(*Customer)
                        ans = append(ans, customer.id)
                }
        }

        // 输出结果
        for _, num := range ans {
                fmt.Println(num)
        }
}

时空复杂度

时间复杂度：O(K+MlogK)。M为调用"p"的次数，K为客户总人数，入堆和出堆的复杂度均为O(logK)，M次排序共花费O(MlogK)。另外还存在K次输入客户信息。

空间复杂度：O(K)。heap优先队列所占空间。