2024华为OD试题及答案-A004-插队

题目描述

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

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

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

输入描述

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

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

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

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

输出描述

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

用例

问题解析

题目描述了一个银行排队处理业务的场景，不同优先级的客户可以插队到优先级较低的客户前面。当多个客户同时到达时，优先级高的客户先处理，如果优先级相同，则按照到达顺序处理。

输入描述：

• 第一行是一个正整数 n，表示输入的序列中的事件数量 (1 ≤ n ≤ 500)。
• 接下来有 n 行，每行第一个字符为 a 或 p。
  • 当字符为 a 时，后面会有两个整数 num 和 x，表示到来的客户编号为 num，优先级为 x。
  • 当字符为 p 时，表示当前优先级最高的客户去办理业务。

输出描述：

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

实现思路：

C++ 实现

下面是用 C++ 实现该逻辑的代码：

#include <iostream>
#include <queue>
#include <vector>
using namespace std;

// 定义客户结构体
struct Customer {
    int num;  // 客户编号
    int priority;  // 优先级
    int order;  // 到达顺序

    // 自定义比较函数，使优先队列根据优先级和到达顺序排序
    bool operator<(const Customer& other) const {
        if (priority == other.priority) {
            return order > other.order;
        }
        return priority < other.priority;
    }
};

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

    priority_queue<Customer> pq;
    int order = 0;

    for (int i = 0; i < n; ++i) {
        char type;
        cin >> type;

        if (type == 'a') {
            int num, priority;
            cin >> num >> priority;
            pq.push({num, priority, order++});
        } else if (type == 'p') {
            if (!pq.empty()) {
                Customer top = pq.top();
                pq.pop();
                cout << top.num << endl;
            }
        }
    }

    return 0;
}

代码说明：

1. Customer 结构体：用于存储客户编号、优先级和到达顺序。定义了 < 运算符用于优先队列的排序。
2. main 函数：
   • 读取输入的事件数量。
   • 根据事件类型 a 或 p 执行相应操作。
   • 使用优先队列 pq 处理客户的优先级和顺序，确保优先级高的客户优先处理，优先级相同时按到达顺序处理。

输入输出示例：

• 输入：

4
a 1 3
a 2 2
a 3 2
p

输出：

1

该程序能够根据输入的事件序列正确处理银行客户的业务顺序。