PTA L2-017 人以群分：排序加前缀和轻松破解分组极值题

PTA L2-017 这个题我第一次看到“人以群分”这个名字的时候以为又要搞什么高深的分类算法。把数据范围和对输出格式的要求仔细读完之后才发现它就是一道非常典型的“想清楚策略之后代码反而很小”的比赛题。给你 n 个人的活跃值要求分成外向、内向两组让人数差尽可能小同时让两组平均活跃值的差尽可能大最后输出两组人数和这个平均差。枚举肯定不现实正解思路其实就一句话排序然后在前缀和上做两个候选切分。下面我会把推导过程、可直接提交的 Java 做法、以及我实际提交时踩过的各种坑一起写出来。1. 题目拆解先想清楚再动手1.1 表面是分组实际是极值问题题目给的是一个长度为 n 的正整数序列每个数代表一个人的活跃值。需要把所有人分成两个非空集合一个叫 Outgoing外向一个叫 Introverted内向。两个目标同时出现时优先级非常明确两组人数差值尽量小。在人数差值已经最小的前提下两组平均活跃值之差尽量大。很多人第一反应是“每组选几个人”脑子容易卡住因为人数一旦不确定似乎就要把所有分组方式都枚举一遍。n 稍微大一点比如 10 万个人枚举全世界也不可能在时限内跑完。所以必须把策略压缩成几个候选。我把这个题看作典型的“排序后前缀和取极值”题。原序列本身无序所以第一步是先排序。只要排完序整个问题的几何结构就出来了如果要让内向组的平均值尽可能低、外向组的平均值尽可能高内向组应该拿连续的一段最小值外向组拿剩余的最大值。这里有一个很容易忽略的点题目把平均活跃值高的一方叫 Outgoing低的一方叫 Introverted。所以不是随便把人数少的一边当外向而是哪边平均值高哪边才是外向。1.2 人数差的“最小”到底有几种设内向组人数为 k外向组人数就是 n - k。两边人数差为 |n - 2k|。当 n 为偶数时最理想的就是 k n / 2两边人数完全一致人数差为 0。这没有第二种选择。当 n 为奇数时比如 n 5k 可以是 2 或 3两种方案的人数差都是 1。这个“1”已经是不能再小的了。进一步看n 101 时k 可以是 50也可以是 51两者人数差也都一样是 1。所以奇数情况下我们总共只需要比较两个候选方案候选 A内向组取前 n / 2 个最小的人。候选 B内向组取前 n - n / 2 个最小的人。剩下的人自然就是外向组。这里不需要考虑“内向组拿的人不连续”这种排列组合因为对于一个固定人数 k想要让内向组平均值最小选前 k 个最小值就是全局最优想要让外向组平均值最大剩下的最大值也是同一个集合。组内怎么排序不影响平均值只影响最终分组输出而题目并不要求逐个人输出。1.3 为什么不是“随便切一刀”这是最容易写出假代码的地方。很多人知道要排序但排序后直接一刀切在 n / 2 的位置奇数 n 就不一定对了。因为当 n 是奇数时“人数差最小”给了两个可接受的分组人数而这两个分组人数对应的平均值差可能不同。比如数组 [1, 2, 3, 10, 20, 30, 100]n 7两个候选分别是内向组取 3 个最小即 [1, 2, 3]外向组取 [10, 20, 30, 100]。内向组取 4 个最小即 [1, 2, 3, 10]外向组取 [20, 30, 100]。第一种的平均差约为 38第二种的平均差约为 46明显第二种更优。所以奇数时一定要把两个候选都算一遍。只看 n / 2 一刀切遇到这种数据就会掉分。2. 核心推导为什么排序后只用看两种分组2.1 前缀和就是一把钥匙排序之后我们已知第 i 个人的活跃值是 a[i]。因为所有内向候选都来自“最前面的连续一段”只要提前算好前缀和 pre[i]前 k 个人的活跃值总和就能直接拿到。假设总活跃值为 total内向组人数为 k外向组人数为 n - k。那么内向组平均值 pre[k] / k外向组平均值 (total - pre[k]) / (n - k)平均值差 (total - pre[k]) / (n - k) - pre[k] / k把这两个分数加起来通分会得到平均值差 (total × k - n × pre[k]) / (k × (n - k))这个通分形式很有用。因为最终要比较两个候选方案的大小如果全部用浮点数 double 比较在 n 很大时其实也基本安全但作为比赛代码我更喜欢用分数精确比较。两个分数的号码和分母都不会超过 long 的范围但两个分数相乘交叉比较时有可能会超过 long所以最稳的办法是用 Java 自带的 BigInteger 只做两次交叉乘法。整个程序没有循环里的大数运算性能可以忽略。2.2 平均值差正负问题上面这个通分公式默认内向组的平均值低于外向组也就是外向组拿的是剩下的较大值。排序后让内向组拿前 k 个最小值这个条件天然成立因此算出来的平均值差一定是正数。后面的输出可以直接用这个正值。实际操作中有的人会把内向、外向人数搞反导致 pre[k] 选成比较大的那一段算出来的平均值差是负数输出错得更隐蔽。我的习惯是先确定内向人数 k再用 pre[k] 取前 k 个最小值最后输出外向人数 n - k。这样思路是一条直线不容易左右颠倒。2.3 我为什么不用 double 来选方案有些题解直接比较两个 double 的大小然后输出 double 格式。边界情况大多数没事但 PTA 的老题目数据构造比较随意如果不幸出现两个候选平均值差非常接近、double 误差还恰好翻转大小的情况就会栽在方案选择上。用 BigInteger 交叉相乘之后方案选择完全不依赖浮点精度。最后输出平均值差的数值时再用 double 转成题目需要的格式。这样做兼顾了“选方案必须准”和“最终输出按题目格式”两点。比较候选 k1 和 k2 时不需要真的算小数 差值1 / 分母1 与 差值2 / 分母2 等价于比较 差值1 × 分母2 与 差值2 × 分母13. Java 满分代码与关键实现3.1 一份可以直接提交的参考代码下面这版代码我按常见评测环境整理过。输入读取没有用 Scanner而是用 BufferedReader 手写了一个只读正整数的快速 nextInt数值用一个 int 数组存排序用 Arrays.sort(int[])前缀和用 long 数组。整个提交逻辑简洁时间开销主要就是排序。import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.math.BigInteger; import java.util.Arrays; import java.util.Locale; public class Main { static int n; static long total; static long[] pre; private static int nextInt(BufferedReader in) throws IOException { int c; while ((c in.read()) ! -1 (c 0 || c 9)) { // 跳过非数字 } int v 0; while (c 0 c 9) { v v * 10 (c - 0); c in.read(); } return v; } private static BigInteger numerator(int k) { // 通分后的分子total * k - n * pre[k] long num total * k - (long) n * pre[k]; return BigInteger.valueOf(num); } private static BigInteger denominator(int k) { return BigInteger.valueOf((long) k * (n - k)); } private static int compareTwo(int k1, int k2) { BigInteger left numerator(k1).multiply(denominator(k2)); BigInteger right numerator(k2).multiply(denominator(k1)); return left.compareTo(right); } private static double averageDiff(int k) { long num total * k - (long) n * pre[k]; long den (long) k * (n - k); return 1.0 * num / den; } public static void main(String[] args) throws IOException { BufferedReader br new BufferedReader(new InputStreamReader(System.in)); n nextInt(br); int[] a new int[n]; total 0; for (int i 0; i n; i) { a[i] nextInt(br); total a[i]; } Arrays.sort(a); pre new long[n 1]; for (int i 0; i n; i) { pre[i 1] pre[i] a[i]; } int k1 n / 2; int k2 n - k1; int introvertedCount k1; if (compareTwo(k2, k1) 0) { introvertedCount k2; } int outgoingCount n - introvertedCount; double diff averageDiff(introvertedCount); System.out.println(Outgoing #: outgoingCount); System.out.println(Introverted #: introvertedCount); System.out.printf(Locale.ROOT, Diff %.1f%n, diff); } }如果题目要求第三行的平均值差保留整数把最后一行改一下即可比如改成System.out.printf(Locale.ROOT, Diff %.0f%n, diff);。关键是前面的方案选择逻辑和人数输出不要动。3.2 代码里几个容易被忽视的细节第一pre[k]表示前 k 个元素的和。前缀和数组我开的是long[n 1]下标从 0 开始pre[0] 0所以取前 k 个时直接用pre[k]不是pre[k - 1]。这个下标错位在比赛里非常常见写出来后要立刻用一个小数据验一遍。第二numerator里的乘法要小心类型。total * k两个都是 long没问题n * pre[k]中 n 是 int虽然 int 会自动提升为 long但为了明确表达我写成了(long) n * pre[k]。如果不加这个强转在某些不好的写法里可能先按 int 相乘再溢出这是致命的。第三排序和分组人数输出要保持一致。我固定用“内向人数 k”作为计算锚点排序后从小到大取 pre[k]那么外向人数自然就是 n - k。这样输出时Outgoing #: outgoingCount放在前面Introverted #: introvertedCount放在后面不要写反。3.3 输入读取为什么要自己写PTA 的 Java 提交经常被 Scanner 卡到超时。Scanner 对字符流做了很多便捷处理内部还有各种正则判断数据量一旦到了 10 万级别会白白吃掉不少时间。用BufferedReader手写整数解析是所有竞赛 Java 选手的基本操作。我写nextInt时默认输入都是正整数。题目里的活跃值确实是正整数所以这段代码可以安全使用。假如哪天遇到负数值需要在里面加符号判断但本题不需要保持短小精悍更合适。4. 现场实测把容易错的点一个个排除4.1 偶数用例输入4 1 2 100 101排序后是 [1, 2, 100, 101]。内向组 2 人取前 2 个 [1, 2]平均值 1.5外向组 2 人取 [100, 101]平均值 100.5差值是 99。代码会输出Outgoing #: 2 Introverted #: 2 Diff 99.0这个用例主要是验证人数差为 0 时分组是否严格按照最小和最大来选。如果输出 Diff 数值不对说明前缀和取错段了。4.2 奇数用例输入5 1 2 3 4 5排序后 [1, 2, 3, 4, 5]。两个候选内向 2 人取 [1, 2]外向 3 人取 [3, 4, 5]平均值差 2.5。内向 3 人取 [1, 2, 3]外向 2 人取 [4, 5]平均值差也是 2.5。这个用例的问题是并列解。代码里我默认取 k1也就是内向组人数较少的那一种。实际评测时如果题面没有额外说明“输出任意一个解即可”这类并列数据就需要自己额外谨慎。很多 PTA 题目对并列解会有明确说法提交前先看题面。4.3 奇数不对称用例输入7 1 2 3 10 20 30 100排序后 [1, 2, 3, 10, 20, 30, 100]。内向 3 人取 [1, 2, 3]平均值 2外向 4 人平均值 40差值 38。内向 4 人取 [1, 2, 3, 10]平均值 4外向 3 人平均值 50差值 46。代码应该输出 46 那套方案。如果只按 n / 2 一刀切就输出了 38直接失分。用这个用例验证非常重要。4.4 极限规模用例构造 n 100000 个从 1 到 100000 连续的数排序、前缀和、BigInteger 交叉比较都跑的很快。实测下来在常见 PTA Java 环境下总耗时远小于时限真正耗时大头在Arrays.sort的原始数组排序。手写快读和缓冲输出在这个量级没有压力。有一点要提醒自己不要为了追求极限性能去手写快速排序。Java 自带的Arrays.sort(int[])是双轴快排对基本类型数组已经做过大量优化自己写的排序大概率更慢还容易写出边界 bug。用官方库是比赛里的正确选择。5. 优化、提交与赛后复盘5.1 为什么前缀和只需要一个数组计算平均值差时需要pre[k]也就是前 k 个元素的和。我没必要开二维数组也不需要额外保存子数组副本。前缀和数组 pre 配合 total能在 O(1) 时间拿到任意候选方案的分子和分母。整个算法复杂度是排序的 O(n log n) 加上后面两次 O(1) 候选比较空间复杂度 O(n)。5.2 关于输出格式的细节输出三行文本很固定但平均差那一行是否能被 PTA 接受取决于评测方式。我在代码里默认保留一位小数并加了Locale.ROOT防止某些环境默认语言把小数点显示成逗号。如果题目要求整数输出把格式符改成%.0f就行但最好不要在输出里自己拼字符串做四舍五入因为printf会按标准规则处理。另外Outgoing #:和Introverted #:两行里面冒号后面有空格。这种字符串比对题空一个字符都会变成 Wrong Answer所以最后一定要用样例输入核对一遍完整输出不要只盯 Diff 数字。5.3 最容易在比赛现场翻车的三个点第一个点是忘记奇数情况下有两个候选。很多人写完偶数样例通过后直接交奇数样例如果恰好是两个候选平均值差一样也看不出来问题一旦遇到不对称数据立刻丢两三个测试点。第二个点是total - pre[k]算的是外向组总和不是外向组平均值。输出 Diff 时要除以人数或者直接用我代码里的通分公式。直接用总和差去当平均值差在两边人数相同时不容易发现在奇数时就会出错。第三个点是读取输入时假设所有数据都在同一行。用readLine()一次读一行虽然快但如果出题人构造的数据出现换行比如每行只放几个数StringTokenizer读不到下一行就崩了。我这里手写的nextInt按字符读取天然支持任意空白符分隔算是一劳永逸的解法。5.4 赛后复盘建议把这道题和同类的“排序 前缀和”题放在一起对比会很有收获。这类题的共同点是题目描述很长看起来像复杂搜索但只要把目标函数变成数学式子就能发现输入顺序无关直接排序做极值。我自己做过几次之后最大的体会是不要一上来就写枚举代码先把“人数差最小有几个候选”推清楚再把手写快读和输出格式固化好。这个题没有高深的数据结构难点全在数学转换和细节稳不稳。把这几点守住Java 拿满分并不难。