刷PTA团体程序设计天梯赛题单的Java选手大概率都跟L2-009抢红包这道题交过手。表面看它只是一道模拟加排序的简单题但它把Java在OJ上的两个经典痛点全凑齐了大输入量下Scanner的恐怖开销以及用浮点数记账带来的精度隐患。很多Java新手在这道题上拿不到满分不是不会写逻辑而是栽在TLE和WA这些与算法无关的地方。这篇文章我按“建账、记流水、排序、输出”四个环节拆开讲把一份可以直接提交的Java写法完整拿出来并解释每一步为什么要这么做。适合正在备赛天梯赛的选手、刚开始用Java刷OJ题的初学者以及所有被L2-009卡过超时或格式错误的人参考。1. 为什么这道题在Java手里容易翻车I/O与记账两大坑1.1 题目到底让干什么参与人数记为N编号从1到N每人一行输入发红包记录。每行开头是K表示这个人总共发了K个红包后面跟着K组数据每组是“抢到红包的人编号 红包金额”。金额是两位小数单位是元。最终要输出N个人的“净收入”也就是抢到的总金额减去发出去的总金额同时统计每个人抢到了几次红包。排序规则是净收入从高到低收入相同按抢到次数从高到低如果还相同按编号从小到大。这里有个容易忽略的点输出的是所有人不是只输出参与过抢红包或发红包的人。没参与的人净收入为0抢到次数为0也要出现在最终结果里。如果你只把参与过的人收集起来排序输出行数就不对直接WA。1.2 用Scanner读二十万个tokenJava已经输了一半K的上限是20N的上限是10000最坏情况下整个输入里有20万组“编号金额”数据也就是40万个token。如果用Scanner的nextInt()和nextDouble()去读单次IO操作的开销会被放大得非常明显。Scanner内部的正则解析和缓冲机制在毫秒级输入量下看不出来但一旦到几十万token和BufferedReader的差距立刻就拉开了。我早期用Scanner写这道题排序逻辑完全正确但提交就是卡在超时边缘。后来把输入换成BufferedReader加StringTokenizer同样的算法逻辑耗时明显降了一个量级。这个优化不是玄学而是Java读入方式本身的性能差异。1.3 用double记钱看着方便算着心惊题目里金额是“元”为单位的两位小数比如5.10元。如果直接用double存然后做加减等到最后比较大小、格式化输出时很容易出现类似509.99999999999994这种残影。更稳妥的做法是全部换算成“分”用整数类型long来记账。5.10元读进来以后直接变成510分加减全是整数运算没有任何精度损失。输出时再除以100.0用String.format(%.2f, ...)还原成两位小数。这一步是整个程序正确性的地基后面所有排序和比较都建立在整数记账之上。2. 把红包账本落成数据结构从输入到净收入的流转2.1 用对象数组还是三个平行数组N最大10000完全没必要为了省内存玩三个平行数组加手写排序。我直接定义了一个Person内部类字段就三个id、money单位是分、cnt抢到次数。初始化为new Person(i 1, 0, 0)把所有N个人都放进数组。对象数组在这种数据规模下开销可以忽略不计。更重要的是直接用Arrays.sort配合自定义比较器就能完成三关键字排序代码可读性和维护性比三个平行数组高出一截。刷题不是写生产系统这种级别的封装完全够用。2.2 一行输入里的账务流转读入逻辑是外层循环N次第i行代表编号为i1的那个人发红包。内层循环K次每一笔都要做三件事发红包的人扣钱people[giver].money - fen抢红包的人加钱people[receiver].money fen抢红包的人次数加一people[receiver].cnt有人会问“发红包的人自己要不要在数组里先初始化为0”需要的因为Person构造时已经把所有字段置零了。每一行输入里的发红包者就是当前循环下标i直接在people[i]上扣钱即可。2.3 金额为什么必须用long而不是int有人觉得N最大10000K最大20每笔金额至多几十元int够用。但最坏情况不能这样算10000个人每个人发20个红包每个红包金额如果达到千元量级一个人单是发出去的钱就可能突破2^31。用int很容易在极端数据下溢出变成负数参与排序导致结果完全错乱。我用long不是因为N10000而是因为任何一笔金额乘以可能的交易次数后都可能超过int的表示范围。用long是最没有心理负担的选择。下面用一个自造的5人样例说明账务流转过程不是官方样例但逻辑完全一致5 2 2 5.10 3 3.20 1 1 4.00 2 2 2.00 4 1.00 1 5 5.00 0按我的代码逻辑走一遍各人账本变化是编号发出总金额抢到总金额净收入抢到次数1830分400分-430分12400分710分310分23300分320分20分14500分100分-400分150500分500分1注意编号1净收入-430分编号4净收入-400分排序时-400分要排在-430分前面因为大的数值在前。这一条后面排序时用得上。3. 三关键字排序的正确姿势比较器的方向感别搞反3.1 一次排序搞定三个条件Arrays.sort的自定义比较器是这道题最容易写错的地方。排序规则按优先级排列净收入从高到低收入相同看抢到次数从高到低还相同看编号从小到大比较器的写法是Arrays.sort(people, (a, b) - { if (a.money ! b.money) { return Long.compare(b.money, a.money); } if (a.cnt ! b.cnt) { return Integer.compare(b.cnt, a.cnt); } return Integer.compare(a.id, b.id); });这里有个很容易绕晕的点。Arrays.sort在比较两个元素a和b时如果比较器返回负数表示a应该排在b前面。Long.compare(b.money, a.money)做的事情是把b当作第一参数、a当作第二参数。当b.money大于a.money时Long.compare(b.money, a.money)返回正数也就是a排在b后面最终结果是钱多的排前面。这个写法等同于“单调递减”但初看很容易反应不过来。3.2 为什么不能用减法代替compareLong.compare(b.money, a.money)和return (int)(b.money - a.money)看起来都行但后者有隐患。long相减后强转成int一旦金额差超过int范围就溢出。虽然到这一步每个字段本身都在long范围内但两个long相减的结果完全可能超出int。Integer.compare和Long.compare是JDK自带的静态方法语义清晰不会溢出刷题时用它们最稳。3.3 排序结果对照自造样例按我前面那个5人样例排序后输出顺序是位次编号净收入元抢到次数155.001223.102330.20144-4.00151-4.301这里可以看到一个细节编号4和编号1收入都是负数但-4.00大于-4.30所以编号4排在编号1前面。如果比较器里的收入降序写反了这两个位置就会互换输出直接WA。4. 不超时的Java提交版完整代码4.1 可提交版本下面的代码是我整理后的最终版本类名Main可以直接提交。完整逻辑包含BufferedReader读入、字符串解析金额、long记账、三关键字排序和StringBuilder输出。import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.Arrays; import java.util.StringTokenizer; public class Main { static class Person { int id; long money; int cnt; Person(int id, long money, int cnt) { this.id id; this.money money; this.cnt cnt; } } public static void main(String[] args) throws Exception { BufferedReader br new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st new StringTokenizer(br.readLine()); int n Integer.parseInt(st.nextToken()); Person[] people new Person[n]; for (int i 0; i n; i) { people[i] new Person(i 1, 0, 0); } for (int i 0; i n; i) { st new StringTokenizer(br.readLine()); int k Integer.parseInt(st.nextToken()); for (int j 0; j k; j) { int who Integer.parseInt(st.nextToken()) - 1; int fen parseFen(st.nextToken()); people[i].money - fen; people[who].money fen; people[who].cnt; } } Arrays.sort(people, (a, b) - { if (a.money ! b.money) { return Long.compare(b.money, a.money); } if (a.cnt ! b.cnt) { return Integer.compare(b.cnt, a.cnt); } return Integer.compare(a.id, b.id); }); StringBuilder sb new StringBuilder(); for (Person p : people) { sb.append(p.id) .append( ) .append(String.format(%.2f, p.money / 100.0)) .append( ) .append(p.cnt) .append(\n); } System.out.print(sb); } static int parseFen(String s) { int dot s.indexOf(.); if (dot -1) { return Integer.parseInt(s) * 100; } int yuan Integer.parseInt(s.substring(0, dot)); String dec s.substring(dot 1); if (dec.length() 1) { return yuan * 100 (dec.charAt(0) - 0) * 10; } return yuan * 100 Integer.parseInt(dec.substring(0, 2)); } }4.2 字符串解析金额为什么比Double.parseDouble稳题目输入金额固定两位小数标准做法可以是(int) Math.round(Double.parseDouble(s) * 100)大多数情况也能过。但我推荐parseFen这个字符串解析的方法原因很简单它从头到尾不经过浮点数。Double.parseDouble(5.10)拿到的值不是精确的5.10而是最接近5.10的二进制浮点数。乘100后得到509.99999999999994这种结果必须靠Math.round打补丁。题目数据虽然都是两位小数round基本能救回来但字符串解析是零误差方案而且代码量只多几行为什么不直接用更稳的那个呢。4.3 StringTokenizer的正确使用姿势StringTokenizer默认按空格和制表符切分。读取每一行后先new StringTokenizer(br.readLine())再用nextToken()拿字符串nextInt()并不存在需要自己Integer.parseInt转换。这样做比String.split( )更快因为split会生成一个字符串数组而StringTokenizer是惰性解析。一个小细节第一行读完后st已经被消费后面每行都要重新赋值为new StringTokenizer(br.readLine())。我见过有同学把StringTokenizer写在循环外面结果所有数据都从第一行切后面全读不到。4.4 输出优化StringBuilder攒一批再交输出部分不能直接在循环里System.out.printf因为System.out是带缓冲的但每次调用都有同步和格式化开销。10000行输出用printf也不是必挂但没必要冒险。StringBuilder把结果全部攒成一个字符串最后一次性System.out.print这是OJ Java题的标准操作。String.format(%.2f, p.money / 100.0)在10000次这个量级完全够快。有人担心String.format很慢其实慢的是大量IO调用格式化本身的消耗在这里可以忽略。5. 从TLE到AC三种写法的实测差异5.1 第一种写法Scanner全线拉满我第一次提交就是标准的Scanner nextInt nextDouble System.out.printf。在N10000、K20的满规模随机数据下本机跑起来就已经能感到明显卡顿提交后果不其然是TLE。问题不在排序排序10000个对象毫秒级完成问题全在Scanner反复做字符解析以及printf的格式化输出上。Scanner的nextDouble要处理正则匹配和浮点解析比nextToken慢得多。40万个token逐个解析累积时间非常可观。如果把金额当作字符串读入再自己解析能省掉浮点解析的开销。5.2 第二种写法BufferedReader加StringTokenizer但不改输出只换输入输出还是循环System.out.printfTLE问题基本能缓解但输出量大的时候仍可能逼近极限。我记得当时在本地用随机数据压测循环printf和StringBuilder的输出耗时差距可能是几倍。OJ的Java时间限制往往卡得很紧能省则省。5.3 第三种写法全量优化后的稳定版我最后提交的版本就是上面的完整代码。实测在我本机跑满规模随机数据从进程启动到输出结束耗时明显低于第一版。这个版本的核心优势有三点优化点作用BufferedReader StringTokenizer减少字符流到内存的拷贝和解析开销字符串解析金额完全避开浮点数转换和精度问题StringBuilder攒批输出把10000次IO调用压缩成1次三个优化合在一起整体耗时几乎只受“读文件排序格式化”本身限制在N10000这个规模上留出了充足的余量。6. 提交前的WA自查清单负数输出、漏人、精度一个都不能少6.1 先确认输出行数是不是N行这是WA率最高的一处。题目要求输出所有人不是只输出有收入记录的人。如果用一个ArrayList临时收集参与过的人再对列表排序最后输出的行数就会比N少。读者自己审查代码时先数输出行数如果少于N直接补上未参与者的排序参与资格。6.2 负数的格式化输出要小心p.money / 100.0的结果是doubleString.format(%.2f, ...)能正确处理负数。比如-430 / 100.0 -4.3格式化后是-4.30完全正常。但我见过手动拼字符串的写法例如sb.append(p.money / 100).append(.).append(p.money % 100);这种写法在负数上会翻车。-430 % 100在Java里结果是-30拼接出来变成-4.-30输出格式直接崩溃。所以格式化输出这种脏活累活交给String.format去干比自己拼字符串安全得多。6.3 自己抢自己红包的情况题目没有明确禁止一个人抢自己发的红包。如果数据里出现i给自己发了红包我的代码逻辑是先扣people[i].money - fen再加people[i].money fen净收入不变但cnt会加一。这个行为符合直觉也算一种合理约定。如果审题时发现题目另有说明按题目要求调整即可。6.4 输入行可能有多余空格StringTokenizer会忽略连续空格和行首行尾空白所以输入格式稍微多些空格也不会影响。但如果用split( )连续两个空格就会解析出空字符串导致Integer.parseInt抛异常。这一类隐藏问题用StringTokenizer天然规避。6.5 样例过了不代表全对这道题的样例数据通常很小覆盖不到“所有人输出”“负数排序”“未参与者”这些边界。我自己提交前会用三种特殊数据自测N1且K0、所有人收入全是负数、以及1号给其他所有人各发一个红包。跑完这三组心里会踏实很多。我个人刷题时习惯把这类题的标准读写模板固定下来BufferedReader读行、StringTokenizer切token、StringBuilder输出。遇到任何大输入量模拟题直接套用省去每次重新调试IO的时间。L2-009这道题不藏什么高深算法它更像一个信号天梯赛的L2题目不是只考思维Java选手的工程基本功同样会被纳入考核范围。把这套IO和记账习惯练熟了后面遇到类似题会顺手很多。