PTA L2-009 抢红包题解C结构体与运算符重载实战指南在编程竞赛和在线判题系统中处理复杂数据排序是常见考点。PTA平台的L2-009抢红包题目就是一个典型的多条件排序问题要求我们不仅要计算每个人的净收入还要按照特定规则排序输出。这类题目考察的核心能力包括结构体设计与数据组织多条件排序规则的实现浮点数精度处理运算符重载的应用1. 题目分析与数据结构设计这道题目要求统计N个人之间互相发红包、抢红包的记录最终按照以下规则排序输出收入金额从高到低金额相同时按抢到红包的个数递减前两项都相同时按个人编号递增1.1 关键数据结构我们需要设计一个结构体来存储每个人的相关信息struct Person { int id; // 个人编号 int count; // 抢到红包的次数 double money; // 净收入金额单位分 };这里有几个设计要点使用double存储金额因为题目要求最终输出两位小数金额以分为单位存储避免浮点数运算带来的精度问题单独记录抢红包次数为后续排序做准备1.2 输入处理逻辑题目输入格式为N K N1 P1 ... NK PK ...处理输入时需要注意每个人可能既是发红包者也是抢红包者每次发红包都会影响两个人的金额发红包者减少抢红包者增加同一个人发出的红包每人最多只能抢1次2. 运算符重载实现多条件排序2.1 排序规则分析题目要求的排序规则可以分解为主要排序键money降序次要排序键count降序第三排序键id升序2.2 运算符重载实现在C中我们可以通过重载运算符来实现自定义排序bool operator(const Person other) const { // 比较金额考虑浮点精度 if (fabs(money - other.money) 1e-4) { return money other.money; // 降序 } // 金额相同比较抢红包次数 if (count ! other.count) { return count other.count; // 降序 } // 前两者相同比较ID return id other.id; // 升序 }关键点说明使用fabs比较浮点数设置合理的精度阈值(1e-4)注意不同排序键的升降序要求运算符重载使得我们可以直接使用std::sort进行排序2.3 浮点数精度处理浮点数比较是这类题目常见的坑点。直接使用比较浮点数通常不可靠应该// 不推荐 if (money other.money) // 推荐 if (fabs(money - other.money) 1e-4)精度阈值的选择要根据题目要求本题中金额输出到小数点后2位所以1e-4的精度足够。3. 完整代码实现与解析下面给出完整的解决方案包含详细注释#include cstdio #include algorithm #include cmath const int MAX_N 10010; struct Person { int id; int count; double money; bool operator(const Person other) const { if (fabs(money - other.money) 1e-4) { return money other.money; } if (count ! other.count) { return count other.count; } return id other.id; } } people[MAX_N]; int main() { int n; scanf(%d, n); // 初始化每个人的ID for (int i 1; i n; i) { people[i].id i; } // 处理每个人的发红包记录 for (int i 1; i n; i) { int k; scanf(%d, k); while (k--) { int receiver; double amount; scanf(%d%lf, receiver, amount); // 接收者增加金额和计数 people[receiver].money amount; people[receiver].count; // 发送者减少金额 people[i].money - amount; } } // 排序 std::sort(people 1, people n 1); // 输出结果转换为元为单位 for (int i 1; i n; i) { printf(%d %.2f\n, people[i].id, people[i].money / 100); } return 0; }3.1 代码关键点解析数组初始化使用1-based索引更符合题目编号习惯初始化时设置每个人的ID输入处理外层循环处理每个人的发红包记录内层循环处理每个红包的接收者和金额金额计算接收者money amount,count发送者money - amount排序与输出使用std::sort配合重载的运算符输出时金额除以100转换为元单位4. 常见问题与调试技巧4.1 常见错误浮点数精度问题错误直接比较浮点数相等解决使用fabs和精度阈值排序规则错误错误忽略次要排序条件解决严格按照题目要求实现所有排序条件数组越界错误使用0-based索引但题目是1-based解决数组大小设为N1从1开始使用4.2 调试技巧小规模测试使用题目提供的样例输入验证构造边界情况如所有人金额相同中间输出在处理完输入后输出每个人的金额和计数验证数据读取和计算是否正确排序验证在排序后输出中间结果检查排序是否符合预期规则4.3 性能优化虽然本题N≤10^4数据量不大但良好的编程习惯包括使用scanf/printf比cin/cout更快对于大量数据输入输出有明显优势避免不必要的操作只在必要时进行浮点数比较减少循环中的冗余计算合理使用数据结构本题使用数组足够更复杂情况可考虑更高效的数据结构5. 类似题型扩展掌握了这道题的解法和思路后可以解决许多类似的排序问题5.1 多条件排序问题这类问题的通用解法设计包含所有需要排序字段的结构体根据题目要求重载运算符或编写比较函数注意各排序条件的优先级和升降序5.2 浮点数处理问题涉及金额、分数等需要精确计算的场景确定合适的精度阈值避免直接相等比较考虑是否可以使用整数运算代替5.3 实际应用场景类似的排序需求在实际开发中很常见电商平台的商品排序销量、价格、评分学生成绩排名总分、单科成绩、学号竞赛排名解题数、用时、队伍编号6. 最佳实践与经验分享在解决这类排序问题时有几个实用技巧统一比较函数 除了运算符重载也可以单独写比较函数bool compare(const Person a, const Person b) { if (fabs(a.money - b.money) 1e-4) return a.money b.money; if (a.count ! b.count) return a.count b.count; return a.id b.id; }测试用例设计设计所有人金额相同的情况设计金额和抢红包次数都相同的情况设计极端数据如最大N值代码复用 将排序逻辑封装成通用模板方便类似题目使用templatetypename T void multiSort(vectorT data) { sort(data.begin(), data.end()); }调试输出 在开发过程中添加调试输出帮助理解程序行为#define DEBUG #ifdef DEBUG printf(Debug: person %d money%.2f count%d\n, id, money, count); #endif在实际编程竞赛中这类排序问题出现的频率很高。建议熟练掌握结构体设计、运算符重载和排序规则实现这些都是解决更复杂问题的基础。