J. 构造三角形 详细题解

我们将这三个组依次记为 $A,B,C$。

不妨设 $n_a \le n_b \le n_c$，且 $x_1 \le x_2 \le \dots \le x_n$。 记所有数的总和为 $S = x_1 + x_2 + \dots + x_n$。 我们只需要保证每个组的和都小于 $\dfrac{S}{2}$。

下面是合法分组存在的两个显然必要条件：

• 元素最多的组不会过大： 最小的 $n_c$ 个数之和满足$$x_1 + x_2 + \dots + x_{n_c} < \dfrac{S}{2}$$
• 最大元素不会过大：$$x_n + (x_1 + x_2 + \dots + x_{n_a-1}) < \dfrac{S}{2} $$

而结论是：这两个条件其实也是充分的！ 我们可以证明一个更强的命题。

---

引理

假设我们已经放置了一部分数，这些数都大于等于剩下的所有数。 设当前组 $g$ 的和为 $S_g$，还剩 $n'_g$ 个空位需要填充； 一共还剩 $n' = n'_a + n'_b + n'_c$ 个数，满足 $x_1 \le x_2 \le \dots \le x_{n'}$。

那么，剩余数字存在合法分配方式的充分必要条件是：

1. 任何组都不会过大：对任意组 $g$，

   $$S_g + x_1 + x_2 + \dots + x_{n'_g} < \dfrac{S}{2}$$

2. 最大元素不会过大： 存在某个还有空位的组 $g$（即 $n'_g > 0$），使得

   $$S_g + x_{n'} + (x_1 + x_2 + \dots + x_{n'_g-1}) < \dfrac{S}{2} $$

---

证明

必要性显然。下面证明充分性。

暂时不妨忽略 $n_a\le n_b\le n_c$ 的顺序。 我们可以把当前最大的元素 $x_{n'}$ 放入组 $A$，于是有：

$$S_a + x_{n'} + (x_1 + x_2 + \dots + x_{n'_a-1}) < \dfrac{S}{2} $$

剩下的数可以任意放进另外两组。 如果这两组的和最终都 $<\dfrac{S}{2}$，则已经合法。

否则，不妨设组 $B$ 的和 $\ge \dfrac{S}{2}$。

我们开始在 $B$ 和 $C$ 之间逐个交换可用元素。 如果某一时刻 $B,C$ 的和同时 $<\dfrac{S}{2}$，则合法。

注意：不可能出现“前一刻 $B\ge \frac S2$，下一刻 $C\ge \frac S2$”的情况。 因为当前 $C$ 的和至多为

$$S - \dfrac{S}{2} - x_{n'}$$

交换后它最多减少 $x_{n'}$、至少增加 $1$，因此仍然满足

$$C < \dfrac{S}{2}$$

于是唯一可能是 $B$ 的和始终 $\ge \dfrac{S}{2}$。

同理，如果在 $A$ 与 $C$ 之间交换，$B$ 依然会 $\ge \dfrac{S}{2}$。 如果 $C$ 已经没有空位（$n'_c=0$），就在 $A,B$ 之间交换； 同样不可能一次交换就让 $A\ge \dfrac{S}{2}$。

因此思路是： 我们不断交换，让最小的 $n'_B$ 个数最终落在 $B$ 中。 但这与已知条件

$$S_b + x_1 + x_2 + \dots + x_{n'_B} < \dfrac{S}{2}$$

矛盾。从而充分性得证。

---

构造方法

这个引理也直接给出了构造方案：

• 将元素从大到小依次加入各组；
• 每次选择一个组放入当前元素，使得放入后仍满足引理条件；
• 在排序并预处理前缀和后，每次检查可以做到 $O(1)$。

总时间复杂度为 $O(n\log n)$。