天梯赛刷到 L2-019《悄悄关注》的时候我一开始的想法很简单这不就是读两个集合、算个平均值、再排个序吗结果第一次用 Java 提交大数据点直接超时才意识到这道题真正的考点根本不是算法而是 Java 的 IO 和集合选型。这篇文章就围绕 PTA 团体程序设计天梯赛 L2-019把 Java 满分不超时的完整方案拆开讲包括题面逻辑、超时原因、数据结构选择、可提交代码以及刷 L2 题单时能直接复用的 IO 模板。如果你正在为天梯赛 Java 超时头疼或者想把这题彻底吃透这篇应该能帮到你。1. 题面拆解先搞清楚“谁”才是被悄悄关注的人1.1 输入里的两个集合别把方向搞反《悄悄关注》题面虽然简短但第一次读的时候很容易把判断方向搞反。题目给出的输入大概是这样的第一组一个正整数 N后面跟着 N 个昵称表示用户的公开关注列表第二组一个正整数 M后面跟着 M 行每行是一个昵称和一个整数点赞数表示一批微博记录。输出的条件是昵称按字典序升序输出要求该昵称的点赞数大于所有记录的平均点赞数并且该昵称不在公开关注列表里。关键就在最后这个“不在公开关注列表里”。很多人一看到“悄悄关注”四个字就以为要从 N 个名单里筛选实际上恰恰相反要筛的是“微博记录里的人”不是“关注列表里的人”。换句话说博主能看到某些人的微博、给他们点了赞但这些人并不在他公开的关注列表上那他就是在悄悄关注这些人。题目要你把这批人揪出来。这个逻辑想通之后整道题的判定就非常清楚了一个微博记录里的昵称如果满足两个条件——点赞数超过平均值、且不在公开关注的 N 个昵称里——就进答案。1.2 样例手推一遍筛选条件就清楚了我自己写题的时候习惯先手推一个样例确认题意没理解偏。比如构造这样一组输入3 Tom Jerry Alice 5 Tom 80 Bob 90 Jerry 40 Alice 70 Eve 50先看公开关注列表Tom、Jerry、Alice。再算所有微博记录的总点赞数80 90 40 70 50 330平均就是 330 / 5 66。逐条看记录Tom在公开关注列表里排除Bob不在列表里点赞 90 大于平均 66满足条件Jerry在公开关注列表里排除Alice在公开关注列表里排除Eve不在列表里但点赞 50 小于平均 66不满足。最终输出一个 Bob。如果我把 Bob 的点赞改成 60所有记录都找不到满足条件的昵称那么输出就是固定的那串英文提示 “Bing Mei You”。这个输出很多同学第一次写错后面我会专门讲。1.3 “平均值”到底是哪个平均值还有一个细节容易忽略平均值分母是 M也就是所有微博记录的条数而不是去重后的昵称个数。什么意思如果同一个人出现了两条记录比如“C 10”和“C 20”平均值分母是这两条都算进去而不是把 C 算成一个人、分母减一。这一点在写代码的时候要体现在累加逻辑上。至于同一个人多条记录到底该不该合并题目语境不同处理方式也不同。大多数题解的做法是用 Map 把同一个人的点赞数累加然后拿“这个人的累计点赞数”和“所有记录的平均点赞数”比较。这样即使题面保证每个人只出现一次代码也不会出错如果出现多次累加逻辑也能正确覆盖。后面第 5 章我会再展开这个坑。2. 为什么同样的思路C 秒过、Java 却总超时2.1 时间限制与 Java 的启动开销天梯赛的题目时间限制通常是为 C 选手设计的Java 虽然一般会放宽到 2~3 倍但依然不算宽裕。L2-019 这种题算法本身复杂度很低大数据点能卡住的只有 IO 和集合操作。Java 选手最容易犯的错就是算法思路完全正确复杂度也是 O(N M log M)但提交上去依然超时。原因往往不是算法本身而是读入和输出方式太慢。天梯赛的 Java 题解里IO 优化的重要性经常被低估实际上一道题能不能“满分不超时”很多时候就取决于你怎么读数据、怎么写输出。2.2 Scanner 的隐藏成本Scanner 用起来确实方便nextInt、nextLine 一行代码就把数据读了。但它的性能在竞赛场景下非常吃亏Scanner 的 nextInt 和 next 底层用到正则表达式做解析每次匹配都有额外开销Scanner 内部有缓冲但面对十万、几十万级别的输入时正则解析的累积耗时非常明显使用 Scanner 时经常配合 hasNext 循环每读一个 token 都要做类型判断。我实际对比过同样是读 10 万行数据Scanner 可能要比 BufferedReader StringTokenizer 慢几百毫秒甚至更多。天梯赛里 Java 总共也就一两秒的时间预算这几百毫秒往往就是“超时”和“满分”的分界线。2.3 输出循环里的“慢性毒药”另一个容易忽略的拖累是输出。有人习惯在循环里写 System.out.println(name)每条答案都独立触发一次控制台输出。在 Java 里每次 println 都会调用底层写操作频繁刷新缓冲区在大数据量的情况下慢得离谱。正确的做法是把所有结果拼到一个 StringBuilder 里最后一次性 System.out.print 出去。这样只触发一次真正的输出操作性能差距在小数据量时看不出来一旦答案数量上万体感差异非常明显。2.4 集合用错复杂度直接裸奔这个题的判定核心是“某个昵称在不在公开关注列表里”。如果用 ArrayList 存关注列表然后 contains 去查每次查找都是 O(N)整体复杂度会变成 O(N * M)数据一大直接爆炸。正确做法是用 HashSet哈希查找平均 O(1)。另外输出要求按字典序排序如果手动收集到 List 再 Collections.sort 当然可以但更省事的做法是直接用 TreeMap 或者 TreeSet让容器在插入的过程中自动维护有序性。对于这道题的规模TreeMap 的 O(log M) 插入开销完全可接受换来的是排序逻辑一行都不用写。3. 满分方案的三步设计读入、去重、排序3.1 读入用 BufferedReader StringTokenizer 替换 Scanner我最终选择的读入方案是 BufferedReader StringTokenizer这也是大多数 Java 竞赛选手沉淀下来的模板。它比 Scanner 快又比 StreamTokenizer 稳妥。为什么不用 StreamTokenizerStreamTokenizer 在解析纯数字时确实很快但处理昵称这种字符串时遇到点号、下划线等字符可能出现分词不符合预期的情况。PTA 的昵称大概率是字母数字下划线但既然有更通用、更稳的方案没必要在这个细节上冒险。StringTokenizer 是按空白字符切分拿到的是一个一个的 token完全不受字符内容影响。配合 BufferedReader.readLine() 按行读再用 StringTokenizer 拆既保持了代码简洁又绕开了 Scanner 的正则开销。我这里写了一个比较健壮的读取方式兼容两种输入排版一种是“N 在单独一行第二行才是 N 个昵称”另一种是“N 和 N 个昵称在同一行”。BufferedReader br new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st new StringTokenizer(br.readLine()); int n Integer.parseInt(st.nextToken()); SetString followed new HashSet(); while (followed.size() n) { while (st.hasMoreTokens()) { followed.add(st.nextToken()); } if (followed.size() n) { st new StringTokenizer(br.readLine()); } }这段代码的核心思路是先取第一行开头的 N然后不断从 token 流里拿昵称填入集合直到填满 N 个。如果第一行后面没带昵称token 用完就继续读下一行直到集满 N 个昵称为止。这样不管题面输入格式是哪种都能正确读入。3.2 查重HashSet 把 O(N) 降到 O(1)公开关注列表用 HashSet 存理由很简单后面需要对每条微博记录的昵称做“在不在列表里”的判断这个操作要执行 M 次。HashSet 的 contains 平均时间复杂度是 O(1)整个查重环节就是 O(M)。如果你用 LinkedList 或 ArrayListcontains 要线性遍历最坏情况下 M 次查询每次都扫完整列表复杂度 O(N * M)。数据量只要稍微上来一点这种写法必超时。有人可能会问关注列表不就 N 个名字吗几百个而已怎么会超天梯赛的大数据点经常把 N 和 M 都推到 10 万级别O(N * M) 就是 100 亿次操作Java 根本扛不住。所以不要心存侥幸。3.3 统计与排序TreeMap 自动按字典序排队统计微博记录的时候我用 TreeMapString, Long 来存昵称和点赞数。选 TreeMap 而不是 HashMap 的原因很直接题目要求按字典序输出TreeMap 的 key 天然有序插入时红黑树会维护好顺序最后遍历一遍就是字典序结果完全不需要额外排序。如果你用 HashMap最后还要把符合条件的 key 拿出来扔进 List再 Collections.sort多写两三行不说还容易漏掉排序这一步。TreeMap 的插入是 O(log M)这和“把所有 entry 取出来排一次序”的复杂度是同级的不会有性能问题。用 TreeMap 等于把“统计 排序”两件事合成了一件。统计时用 getOrDefault 做累加兼容同一个人出现多条记录的情况TreeMapString, Long likeCount new TreeMap(); long sum 0; for (int i 0; i m; i) { st new StringTokenizer(br.readLine()); String name st.nextToken(); long x Long.parseLong(st.nextToken()); likeCount.put(name, likeCount.getOrDefault(name, 0L) x); sum x; }每读一条记录就把点赞数加到这个人名下同时把点赞数累加到总和中。这样最后遍历 TreeMap 时每个 key 对应的 value 就是该昵称的全部点赞累计值。3.4 平均值比较用整数乘法绕开浮点精度平均点赞数的计算最直接的想法是 double avg sum * 1.0 / m然后判断 likeCount.get(name) avg。这样写结果上没错但有两个隐患浮点比较在某些边界值处可能产生精度误差比如 1.0 / 3 * 3 不等于 1 这类情况多引入一个 double 类型内存和指令上没意义。更好的写法是用整数乘法做等价变形likeCount.get(name) * m sum原理很简单条件“value sum / m”两边同时乘 m变成“value * m sum”。只要 value 和 m 的乘积不溢出 long这个比较就是精确的。点赞数单条到 10 的 9 次方、M 到 10 的 5 次方乘积也就 10 的 14 次方long 完全装得下。注意这里用的是 long 而不是 int否则 value * m 很容易溢出溢出后可能出现负值判定直接出错。这个细节看起来小但实际提交时真能让人排查半天。4. 可直接 AC 的 Java 代码与逐段说明4.1 完整代码下面这版是我在实际提交中整理出的版本类名 Main无 package 声明JDK 8 及以上都能编译运行。关键点全部标注在注释里import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.HashSet; import java.util.Map; import java.util.Set; import java.util.StringTokenizer; import java.util.TreeMap; public class Main { public static void main(String[] args) throws IOException { BufferedReader br new BufferedReader(new InputStreamReader(System.in)); // 读 N 和 N 个公开关注昵称兼容多种排版 StringTokenizer st new StringTokenizer(br.readLine()); int n Integer.parseInt(st.nextToken()); SetString followed new HashSet(); while (followed.size() n) { while (st.hasMoreTokens()) { followed.add(st.nextToken()); } if (followed.size() n) { st new StringTokenizer(br.readLine()); } } // 读 M 条微博记录 int m Integer.parseInt(br.readLine().trim()); TreeMapString, Long likeCount new TreeMap(); long sum 0; for (int i 0; i m; i) { st new StringTokenizer(br.readLine()); String name st.nextToken(); long x Long.parseLong(st.nextToken()); likeCount.put(name, likeCount.getOrDefault(name, 0L) x); sum x; } // 筛选不在公开关注列表且点赞数高于平均值 StringBuilder sb new StringBuilder(); for (Map.EntryString, Long entry : likeCount.entrySet()) { String name entry.getKey(); long likes entry.getValue(); if (!followed.contains(name) likes * m sum) { sb.append(name).append(\n); } } // 没有满足条件的人时输出固定提示串 if (sb.length() 0) { System.out.print(Bing Mei You); } else { System.out.print(sb.toString()); } } }4.2 核心行注释我单独把几行容易被忽略的代码拎出来说明一下。while (followed.size() n)这段循环是为了兼容“N 单独一行”和“N 与昵称在同一行”两种格式。如果第一行只有 N那么第一次 StringTokenizer 里只有一个 token内层 while 不会被执行外层 if 判断集合没满就继续读下一行填名字。这样写可以避免 set 里多塞进一个数字 token。likeCount.put(name, likeCount.getOrDefault(name, 0L) x)是累加点赞数。getOrDefault 在 JDK 8 引入比手动判断 containsKey 再 get 再 put 简洁得多。用0L而不是0是防止类型自动转换时从 Long 变成 long 再装箱出问题。likes * m sum是平均值判断的整数等价形式。sum 是 longlikes 是 longm 是 int计算时 m 会自动提升为 long 再做乘法所以不会溢出。如果写成 int 乘法数据一大就会翻车。StringBuilder sb收集所有符合条件的人名最后一次性输出。这里有个小细节最后判断sb.length() 0而不是sb.toString().isEmpty()是因为每 append 一个人名都会带一个\n有答案时长度一定大于 0。没有答案时就不会输出多余换行和题目要求的 “Bing Mei You” 保持完全一致。4.3 复杂度与内存开销时间复杂度分三块读关注列表并建 HashSetO(N)读 M 条记录并写入 TreeMapO(M log M)主要开销在红黑树插入最后遍历 TreeMap 做筛选O(M)。总复杂度就是 O(N M log M)这是这道题能达到的最优级别之一。天梯赛 L2-019 的数据规模完全能扛住。空间上HashSet 存 N 个昵称TreeMap 存最多 M 个不同昵称整体 O(N M)。这个题目不会让你爆内存关键是别用 ArrayList 替代 HashSet也别用 Scanner 拖慢 IO。5. 提交前必须检查的三个经典坑5.1 “Bing Mei You”的准确拼写与输出行为这题的固定输出是英文 “Bing Mei You”很多第一次做的同学容易拼错比如写成 “Bing Me You”“Bing Mei You”。我最早就是错在这里Wa 了一个测试点才发现是拼写问题。正确写法是 B-i-n-g 空格 M-e-i 空格 Y-o-u。注意每个单词首字母大写中间是空格不是下划线。输出时不要带多余换行或空格题面一般要求原样输出。用System.out.print(Bing Mei You)而不是println避免末尾多一个换行这样最保险。5.2 同一个人出现多条记录要不要累加关于同一个人是不是会在 M 条记录里出现多次这个题面有时候写得不明确。有些版本说“给出 M 个用户的昵称和点赞数”字面上像是每个人只出现一次但很多题解和测试数据里同一个昵称会出现多次。我建议一律按累加处理。原因很简单如果每个人只出现一次累加和不累加结果完全一样如果出现多次不累加就会漏统计导致这个人总点赞数偏低可能被错误过滤掉。累加的处理方式能同时兼容两种题面没有任何副作用。具体到代码里就是getOrDefault(name, 0L) x而不是put(name, x)直接覆盖。5.3 类名、包名与 JDK 版本兼容天梯赛 Java 提交有几个硬性要求类名必须是 Main不能写 package 声明入口方法必须是 public static void main注意是 String[] 不是 String args 这种无关紧要的小事不要使用 JDK 11 之后新增的语法特性除非你确定评测机支持。PTA 环境通常提供较高版本 JDK但为了稳妥getOrDefault 这种 JDK 8 的写法已经足够别用 var、List.of 这类新特性。另外throws IOException 写在 main 方法上没有问题评测不会因为你抛出异常而判错。如果你本地测试通过、提交却编译错误优先检查这三项。6. 这套打法能带到哪些题上6.1 天梯赛 L2 的通用 IO 模板L2-019 做完之后我把这套 IO 模板固定了下来后面刷天梯赛其他题也一直在用BufferedReader br new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st new StringTokenizer(br.readLine());遇到多行不确定的情况就用“Token 不够就继续读下一行”的思路。这个模板的通用性很强L2 里大量题目都是“先给数量、再给若干字符串或数字”的结构直接套用可以少踩很多 IO 的坑。输出统一用 StringBuilder 累积最后一次性打印。这个习惯一旦养成Java 在天梯赛里的超时概率会明显下降。6.2 “去重 有序输出”是高频套路《悄悄关注》的核心套路是用 HashSet 做存在性判断用 TreeMap 或 TreeSet 维持有序性。这个组合在天梯赛里反复出现尤其是 L2 的字符串处理题。只要看到“判断某个名字是否出现过”“输出按字典序排序”这类要求优先想到这个组合基本不会错。还有一种变体是“按出现次数排序”这时候 TreeMap 就不够用了需要把 Entry 取出来按 value 排序。但去重和有序这两个基础能力依然是核心。6.3 如果数据规模再翻十倍如果题目数据量从 10 万变成 100 万TreeMap 的 O(M log M) 可能成为瓶颈。那时候可以考虑用 HashMap 先统计再把需要的 Entry 放进数组排序排序这个过程用 Arrays.sort 或者 Collections.sort常数比红黑树插入要小一些。不过对于 L2-019 这道题本身TreeMap 完全够用。做题最重要的是先让思路和代码正确不要为了“以后可能更快”去牺牲当前的简洁性。真遇到 100 万级别的题目时间限制一般也会给到相应倍数再用更极致的优化不迟。我个人的习惯是先跑通这版稳定的答案拿到满分之后再思考如果数据加大会怎么写。竞赛里最怕的不是慢而是为了追求不必要的极致优化把代码写复杂后引入了 bug。刷完这题再回看L2-019 的价值不仅在于一个 AC更在于它逼着 Java 选手把 IO、集合选型和边界处理这几个基本功练扎实。后面再遇到 L2 的字符串处理题我基本都是这套打底很少再被“Java 超时”这件事卡住。