题意分析

这道题要求模拟银行客户服务系统，处理不同优先级的客户请求。核心需求如下：

• 客户由唯一标识K和优先级P表示，系统需要支持添加客户、服务最高优先级客户、服务最低优先级客户三种操作（除停止服务外）。
• 输入包含多个请求，最后以请求0结束。对于服务请求（代码2或3），若等待列表为空则输出0，否则输出被服务客户的K。

解题思路

1. 数据结构选择

使用map<int, int>存储客户信息，其中：

• 键为优先级P（自动按升序排序），值为客户标识K。
• map的底层是红黑树，支持O(log n)时间复杂度的插入、删除和查找，适合动态维护有序数据。

2. 核心操作实现

• 添加客户（请求1）：直接将(K, P)存入map，利用map的自动排序特性按P排序。
• 服务最高优先级（请求2）：map的最后一个元素（最大P）对应最高优先级，可通过a.end() - 1获取。
• 服务最低优先级（请求3）：map的第一个元素（最小P）对应最低优先级，可通过a.begin()获取。
• 空列表处理：操作前检查map是否为空，空则输出0。

###标程

#include <iostream>
#include <cstdio>
#include <map>
using namespace std;

map<int, int> client_map;  // 键：优先级P，值：客户K
int request, k, p;

int main() {
    map<int, int>::iterator it;
    while (scanf("%d", &request), request != 0) {  // 读取请求直到遇到0
        if (request == 1) {  // 添加客户
            scanf("%d %d", &k, &p);
            client_map[p] = k;  // 存储K和P的映射
        } else {  // 服务请求（2或3）
            if (client_map.empty()) {  // 等待列表为空
                printf("0\n");
            } else {
                if (request == 2) {  // 服务最高优先级（最大P）
                    it = client_map.end();
                    it--;  // 指向最大P的迭代器
                } else if (request == 3) {  // 服务最低优先级（最小P）
                    it = client_map.begin();  // 指向最小P的迭代器
                }
                printf("%d\n", it->second);  // 输出客户K
                client_map.erase(it->first);  // 删除该优先级的客户
            }
        }
    }
    return 0;
}

关键步骤说明：

1. 输入处理：循环读取请求，直到遇到0时结束程序。
2. 添加客户：使用map[p] = k将客户信息存入，map自动按P升序排列。
3. 获取最高/最低优先级：
   • 最高优先级：map.end()返回尾后迭代器，减1后指向最大的P。
   • 最低优先级：map.begin()直接指向最小的P。
4. 服务与删除：输出客户K后，通过erase(it->first)移除该优先级的客户，确保后续操作不受影响。

算法正确性与效率

• 正确性：
  map的自动排序特性保证了优先级的有序性，因此获取最高/最低优先级的操作是正确的。删除操作确保每个客户仅被服务一次，符合题目要求。

• 时间复杂度：
  每个请求的时间复杂度为O(log n)（map的插入、删除、查找均为O(log n)），适用于题目给定的输入规模（K<10⁶，P<10⁷）。

• 边界情况处理：
  当等待列表为空时，直接输出0，避免访问空容器导致错误。

总结

该方案利用map的有序性和高效操作，简洁地实现了题目要求的客户服务系统。核心在于利用map的自动排序特性快速获取最高/最低优先级客户，并通过迭代器操作完成服务与删除。