P14066 [PO Final 2022] 分组 / Triangeltal 笔记

题目相当于要求构造 $A_{0\dots 2}$，使得 $\underset{a\in A_i}{max}a\le |A_{(i+1)mod3}|$。

右侧不好考虑，从左侧入手。将 $a$ 从小到大排序，假设 $a_n\in A_0$，那么贪心地，$|A_1|=a_n$。

接着考虑确定 $A_2$，枚举 $a_i$ 作为 $A_1$ 的最大值，那么 $A_1$ 肯定贪心地选择 $a_{(i-a_n,i]}$，$A_2$ 选择剩下的前 $a_i$ 小个，保证 $A_2$ $max$ 尽量小。

接下来只剩 $max{A}_2\le |A_0|$ 尽量小这一条件没有满足，由于剩下的全部给 $A_0$ 不影响 $A_0$ 最大值的地位，判断一下即可。