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 = 5，k 可以是 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 拿满分并不难。
