1. 问题背景与核心诉求解析最近在整理一些高校计算机专业研究生复试的机试真题发现北京邮电大学的一道关于“复数集合”的题目出镜率相当高而且常常和“优先队列”这个数据结构绑定在一起出现。这道题本身不算复杂但恰恰是这种“数据结构特定规则”的组合非常考验考生对基础数据结构的灵活运用能力以及将实际问题抽象为计算模型的基本功。很多同学一看到“复数”、“集合”、“优先队列”这几个词堆在一起就有点发懵其实拆解开来每一步都有清晰的逻辑可循。这道题的核心诉求是什么呢简单来说你需要维护一个动态的“复数集合”。这个集合不是普通的集合它有一系列特殊的操作规则其中最关键的规则是当需要从集合中删除元素时不是删除最先加入的也不是删除最后加入的而是删除“模最大的”那个复数。如果存在多个模相同的复数则删除其中“先加入集合”的那一个。这个“按特定优先级出队”的需求正是优先队列Priority Queue的典型应用场景。所以题目的难点不在于复数的运算而在于如何利用优先队列或者更准确地说如何设计优先队列中元素的“优先级比较规则”来满足题目给出的、略显复杂的删除逻辑。2. 优先队列的本质与定制化比较器要解决这个问题我们首先得吃透“优先队列”在这个场景下的玩法。在很多编程语言的标准库中优先队列默认是一个“大顶堆”Max Heap即队首top元素永远是当前队列中“最大”的那个。这里的“大”和“小”完全由我们定义的比较规则来决定。对于整数默认就是数值大小对于字符串可能是字典序。但对于我们自定义的复数结构体我们必须明确告诉优先队列什么叫“大”。根据题目要求删除时的优先级顺序是模长较大的复数优先级更高应该先出队。模长相同时先加入集合的复数优先级更高应该先出队。这里有一个非常关键的细节也是容易踩坑的地方优先队列的“优先级”定义与我们直观理解的“谁该先出去”有时是相反的。我们需要仔细思考堆顶应该存放什么。方案一大顶堆直接定义“优先级高”我们可以定义对于两个复数模长大的“优先级更高”模长相同时进入时间早的“优先级更高”。那么在一个大顶堆中优先级最高的元素就会位于堆顶。当执行删除操作时我们直接弹出堆顶元素这个元素正好就是“模最大若模同则时间最早”的那个完美符合题目要求。这种思路最直观。方案二小顶堆反转比较逻辑我们也可以定义对于两个复数模长大的“优先级更低”模长相同时进入时间早的“优先级更低”。那么在一个小顶堆中堆顶存放的就是“优先级最低”的元素即“模最小若模同则时间最晚”的那个。这显然不符合我们的删除目标。因此如果我们想用小顶堆就需要在比较器里做反向处理或者不直接使用堆顶元素。这种方案比较绕一般不推荐。所以最清晰、最不容易出错的方案就是采用大顶堆Max Heap并自定义比较器让“该被删除的元素”拥有最高的优先级从而位于堆顶。接下来是具体的比较逻辑实现。我们需要为每个复数元素绑定一个唯一的“入队时间戳”或“序号”。在C中我们可以使用std::priority_queue并为其提供一个自定义的比较函数对象仿函数。这个比较函数应该实现“严格弱序”。假设我们有一个结构体Complex包含实部real、虚部imag和入队序号id。那么在比较两个复数a和b时首先比较模的平方避免开方运算带来的精度和效率问题a.modSq a.real*a.real a.imag*a.imag。如果a.modSq b.modSq那么a的模更大a的优先级应该比b高。在实现大顶堆的比较函数时我们定义a的优先级高于b当且仅当a应该排在b前面。对于std::priority_queue它默认使用std::less会构造一个大顶堆其比较是“小于”比较。但自定义比较器时我们返回true表示第一个参数应该排在第二个参数之前。为了构造大顶堆我们希望值大的在前所以当a.modSq b.modSq时比较函数应返回true。如果a.modSq b.modSq显然a优先级低返回false。如果a.modSq b.modSq则比较入队序号id。id小的先入队的优先级应该更高。所以当a.id b.id时返回true。注意这里有一个常见的混淆点。std::priority_queue的模板参数中第三个参数是Compare比较类。默认的std::less会生成大顶堆这意味着队列内部使用“小于”比较来维护堆序如果comp(a, b)返回true则a被认为“小于”b在堆中会排在b的后面不对这里需要纠正一个关键理解。对于默认的std::less它生成的堆是大顶堆即最大的元素在堆顶。其底层实现是如果a“小于”b那么a的优先级就低于b。所以为了让我们“模大且id小”的元素成为最大的即优先级最高我们需要定义一种“小于”关系使得“该被删除的元素”比别的元素都“大”。换句话说在我们的自定义比较器Comp中Comp(a, b)返回true应当表示a的优先级低于b。这样优先级最低的元素会在堆底优先级最高的我们想删除的在堆顶。所以逻辑应该是当a的模平方小于b的模平方或者模平方相等但a.id大于b.id时a的优先级低于b比较函数返回true。这个逻辑需要仔细捋顺否则很容易写出错误的比较器导致结果完全相反。我建议在写代码时先写几个测试用例比如 (模3,id1) 和 (模5,id2)想想谁应该先出队模5的那么在这个比较器里模5的应该“大于”模3的即Comp(模3, 模5)应该返回true表示模3“小于”模5。下面我们会在代码部分具体实现。3. 输入输出处理与程序框架设计明确了核心数据结构我们来看整个程序的流程。题目通常是模拟一个交互系统输入包含多条命令直到遇到特定命令如“Pop”在空集合时或结束符为止。命令有两种Insert命令格式如Insert 1i2或Insert 1-i2。表示向集合中插入一个实部为1虚部为2或-2的复数。Pop命令格式就是Pop。表示从集合中删除并输出那个优先级最高的复数模最大同模则最早加入。输出对应如下执行Insert后输出当前集合中的复数个数。格式如SIZE k其中k为插入后集合大小。执行Pop后如果集合为空输出empty。如果不为空则输出被删除的复数格式如1i2注意虚部为正时输出i为负时输出-i虚部为0或±1时需特殊处理格式然后输出当前集合大小SIZE k。程序框架设计如下定义一个复数结构体Complex包含实部r、虚部i和入队序号idx。定义一个优先队列priority_queueComplex, vectorComplex, Comp其中Comp是我们自定义的比较仿函数。初始化一个计数器idCounter 0用于分配入队序号。循环读入字符串命令cmd。判断cmd的前几个字符是Insert还是Pop。如果是Insert解析后面的字符串提取实部和虚部。这里涉及字符串处理要注意虚部符号和i字符的识别。一个稳健的方法是使用sscanf或字符串查找、分割函数。例如字符串可能是1i2,1-i2,i2实部为01虚部为0-i2实部0虚部-2等。需要全面考虑。根据解析出的实部a和虚部b以及当前idCounter构造一个Complex对象。idCounter自增。将该对象插入优先队列。输出SIZE queue.size()。如果是Pop检查队列是否为空。若空输出empty。若不为空取出堆顶元素queue.top()将其弹出queue.pop()。格式化输出该复数。这里要特别注意输出格式实部直接输出虚部输出时如果虚部b 0则输出i再输出b如果b 0则输出-i再输出-b因为b本身是负数如果b 0则什么都不输出或者只输出实部题目通常要求如果虚部为0则不显示虚部。此外如果虚部绝对值为1通常只输出i或-i不输出数字1。例如1i1应输出为1i1-i1应输出为1-i。这是格式上的一个坑点。输出当前集合大小SIZE queue.size()。4. 关键代码实现与避坑指南理论清晰了我们来看具体实现这里以C为例因为机试环境通常支持C STL。首先定义结构体和比较器。这里采用之前分析的正确逻辑在我们的比较器Comp中operator()返回true表示第一个参数a的优先级低于第二个参数b。这样优先级最高的模最大同模则id最小会位于大顶堆的堆顶。#include iostream #include queue #include string #include cstdio #include cmath using namespace std; struct Complex { int r; // 实部 int i; // 虚部 int id; // 入队序号用于区分同模元素 // 可以顺便缓存模的平方避免重复计算但此题数据量不大也可在比较时计算 // long long modSq; // r*r i*i }; // 自定义比较器 struct Comp { bool operator()(const Complex a, const Complex b) { long long modSq_a 1LL * a.r * a.r 1LL * a.i * a.i; long long modSq_b 1LL * b.r * b.r 1LL * b.i * b.i; // 优先级规则模长大的优先模相同则id小的优先 // 如果a的优先级低于b则返回true if (modSq_a ! modSq_b) { // a模小则a优先级低返回true return modSq_a modSq_b; } else { // 模相同a的id大后入队则a优先级低返回true return a.id b.id; } // 这个比较器用于构造大顶堆堆顶将是优先级最高的元素模最大同模id最小 } }; // 使用优先队列 priority_queueComplex, vectorComplex, Comp pq;接下来是命令解析函数这是另一个容易出错的地方。我们需要处理多种输入格式。// 解析Insert命令后的字符串如 1i2, 1-i2, i2, -i2, 1, -1 bool parseComplex(const string s, int real, int imag) { real 0; imag 0; size_t pos_i s.find(i); if (pos_i string::npos) { // 没有i说明只有实部虚部为0 real stoi(s); imag 0; return true; } // 找到i的位置后分情况讨论 if (pos_i 0) { // 字符串以i开头例如 i2, -i2 // 实部为0 real 0; string imagPart s.substr(pos_i 1); // i后面的部分 if (imagPart.empty()) { // 只有i默认为1 imag 1; } else { imag stoi(imagPart); } // 检查i前面的符号 if (s[0] -) { // 实际上是 -i2 imag -imag; } } else { // i不在开头例如 1i2, 1-i2, -1i3 // 先提取实部部分从开头到i之前最后一个非数字字符通常是或-之后 // 更稳健的做法找到i之前最后一个或-号 size_t op_pos s.find_last_of(-, pos_i - 1); if (op_pos string::npos) { // 没有找到或-说明实部后直接跟i例如 1i2? 这种格式不标准但可能是1i2代表1i2 // 题目通常格式规范我们按规范处理。假设格式为 aib 或 a-ib // 如果找不到符号我们假设实部是整个字符串直到i的前一个字符 string realPart s.substr(0, pos_i); real stoi(realPart); // 虚部是i之后的部分 string imagPart s.substr(pos_i 1); imag imagPart.empty() ? 1 : stoi(imagPart); // 虚部符号这里需要看实部和i之间是否有隐含的。题目输入通常是明确带符号的。 // 这是一个漏洞需要根据题目具体输入约定来调整。最安全的方法是使用sscanf。 } else { // 找到了分隔实部虚部的运算符位置op_pos string realPart s.substr(0, op_pos); real realPart.empty() ? 0 : stoi(realPart); // 处理像 i2 这种情况实部为0 string imagPart s.substr(pos_i 1); imag imagPart.empty() ? 1 : stoi(imagPart); // 确定虚部符号 if (s[op_pos] -) { imag -imag; } } } return true; }实际上上面的解析函数为了覆盖所有情况变得有些复杂。在机试的紧张环境下更推荐使用sscanf或stringstream进行格式化读取前提是题目输入格式严格。如果题目明确说明格式为aib或a-ib其中a和b都是整数b0那么解析会简单很多。但为了鲁棒性我们可以假设输入格式就是aib或a-ib其中a和b都是整数b可能带符号但通常b是正整数符号由前面的或-决定。我们可以这样解析// 更简洁的解析假设输入格式严格为 [实部][或-]i[虚部数字]如 1i2, 1-i2, i2, -i2, 0i5 bool parseComplexSimple(const string s, int real, int imag) { real 0; imag 0; // 尝试用sscanf匹配多种格式 // 格式1: aib 或 a-ib char plus_minus; if (sscanf(s.c_str(), %d%ci%d, real, plus_minus, imag) 3) { if (plus_minus -) { imag -imag; } return true; } // 格式2: ib 或 -ib (实部为0省略) if (sscanf(s.c_str(), %ci%d, plus_minus, imag) 2 (plus_minus || plus_minus -)) { real 0; if (plus_minus -) { imag -imag; } return true; } // 格式3: ib (虚部实部为0且虚部符号为正) if (sscanf(s.c_str(), i%d, imag) 1) { real 0; return true; } // 格式4: -ib if (sscanf(s.c_str(), -i%d, imag) 1) { real 0; imag -imag; return true; } // 格式5: 只有实部 a if (sscanf(s.c_str(), %d, real) 1) { imag 0; return true; } // 如果都不匹配可能是非法输入根据题目要求处理 return false; }主程序逻辑如下int main() { int idCounter 0; string cmd; while (cin cmd) { if (cmd Pop) { if (pq.empty()) { cout empty endl; } else { Complex c pq.top(); pq.pop(); // 格式化输出复数 cout c.r; if (c.i 0) { if (c.i 1) cout i; else cout i c.i; } else if (c.i 0) { if (c.i -1) cout -i; else cout -i -c.i; // 注意这里输出的是-i和虚部的绝对值 } // 如果虚部为0则什么也不加 cout endl; cout SIZE pq.size() endl; } } else if (cmd.substr(0, 6) Insert) { // 提取Insert后面的字符串可能有空格题目通常是一行一个命令 // 假设输入是 Insert 1i2 整体作为一个字符串读入cmd // 我们需要分离出Insert和1i2 // 更常见的输入方式是先读命令字符串cmd如果是Insert再读一个字符串表示复数 string complexStr; cin complexStr; // 读取复数字符串 int real, imag; if (parseComplexSimple(complexStr, real, imag)) { pq.push({real, imag, idCounter}); cout SIZE pq.size() endl; } else { // 处理解析失败但题目通常保证输入正确 } } else { // 其他命令或结束符根据题目要求可能跳出循环 // 例如有的题目以一行0结束 break; } } return 0; }避坑指南与实操心得比较器逻辑是重中之重这是本题的核心考点。一定要在纸上画两个复数按照题目要求的删除顺序确定谁应该先出队然后推导出在比较函数中什么情况下返回true表示第一个参数优先级更低。写完后用几个测试用例验证一下比如插入 (1, i1, id1) 和 (2, i0, id2)模分别是 sqrt(2)≈1.41 和 2显然(2,0)应该先出队。在你的优先队列里堆顶应该是(2,0)。检查你的比较器Comp((1,1), (2,0))应该返回true因为(1,1)模小优先级低。多测试几组同模不同id的情况。输出格式必须严格匹配机试是机器判题格式错误就是零分。特别注意虚部为0时只输出实部。例如3i0应该输出3而不是3i0或30i。虚部为±1时只输出i或-i不输出1。例如1i1输出1i1-i1输出1-i。虚部为正时有号为负时是-号。例如1i2和1-i2。实部为0时也要正确输出。例如0i5输出i5不通常输出i5或i5根据题目示例来。常见的是i5。但我们的输出逻辑是如果实部为0我们输出0吗还是直接以虚部开头例如复数05i通常数学上简写为5i。但在题目中可能需要输出i5或5i这必须看题目示例。我上面给出的代码输出的是0i5或0-i5这可能不符合要求。需要调整当实部为0时不输出“0”直接输出虚部部分。例如实部0虚部5输出i5还是i5如果虚部是-5输出-i5。这里又是一个坑点。务必仔细阅读题目输出说明和样例字符串解析要健壮机试的输入格式通常是规整的但自己写解析函数时要考虑边界情况比如i后面没有数字代表虚部为1i或-i单独出现实部或虚部为负数等。使用sscanf可以简化很多但要注意其返回值匹配的参数数量。数据类型与溢出计算模的平方时r*r i*i可能超出int范围。题目中实部虚部可能是绝对值不超过1000的整数平方和可能达到2e6仍在int范围内约21亿以内。但为了安全使用long long存储平方和是更稳妥的做法尤其是在比较器中。优先队列的底层容器priority_queueComplex, vectorComplex, Comp这里第二个模板参数是底层容器通常用vector。确保Complex结构体是可拷贝的。处理空集合的Pop这是基本逻辑别忘了。5. 测试用例与调试技巧写完代码后必须用多个测试用例验证。自己设计测试用例覆盖以下场景基础功能输入Insert 1i2,Insert 3-i4,Pop,Pop。预期插入后分别输出SIZE 1,SIZE 2。第一次Pop应输出模大的3-i4模5然后输出SIZE 1。第二次Pop输出1i2模≈2.236SIZE 0。同模比较输入Insert 1i2(id0, 模√5≈2.236),Insert 2i1(id1, 模√5≈2.236),Pop。预期两个复数模相同应该删除先插入的(id0)即1i2。虚部为0或±1的格式输入Insert 1i0,Insert 2-i1,Pop,Pop。预期第一次Pop输出2-i注意不是2-i1第二次Pop输出1注意不是1i0。实部为0的格式输入Insert 0i3,Insert 0-i4,Pop。预期输出-i4模4还是0-i4根据题目要求调整。通常可能输出-i4。空集合Pop输入Pop。预期输出empty。复杂序列混合Insert和Pop验证动态过程是否正确。调试时可以在关键位置打印中间变量比如每次Insert后打印队列中所有元素的模和id需要遍历队列但优先队列不能直接遍历可以临时拷贝出来打印或者每次Pop前打印堆顶元素的信息确保比较器工作符合预期。6. 性能分析与扩展思考对于机试题数据规模通常不会太大priority_queue的插入和删除操作都是 O(log N) 的复杂度完全够用。这道题的重点在于正确实现逻辑而非优化性能。不过我们可以做一些扩展思考如果要求实时查询集合中模最大的复数但不删除怎么做这就是优先队列的top()操作O(1) 复杂度。如果删除规则变为“模最小的”呢只需要修改比较器将模的比较方向反过来即可。或者更简单使用小顶堆priority_queueComplex, vectorComplex, greaterComplex但需要重载Complex的运算符其逻辑也是定义“优先级低”的顺序。如果复数实部虚部是浮点数怎么办比较模大小时要注意浮点数的精度问题。通常使用平方和比较避免开方。对于浮点数直接比较平方和即可但要注意溢出问题浮点数有范围。同模判断不能直接用要使用fabs(a-b) eps的形式。除了优先队列还有其他数据结构能实现吗理论上任何能维护有序集合的数据结构都可以比如平衡二叉搜索树set或multiset但需要自定义排序规则。插入和删除也是 O(log N)但代码可能更直观因为set本身有序最大元素可以直接用rbegin()获取。不过题目通常点名“优先队列”考察的就是对这个特定数据结构的应用。这道“复数集合”题本质上是一个“最大堆或带自定义优先级的最大堆”的模拟应用题。它把数据结构理论和简单的数学计算、字符串处理结合在一起非常经典。在准备复试机试时这类题目值得反复练习直到能快速、准确、一次性地写出无bug的代码。理解清楚比较器的定义处理好输入输出的细节你就拿下了这道题的关键分。