CF1949K Make Triangle
题目描述
已知 $n$ 个数 $\{x_i\}$,求任意一种把它们分成数量分别为 $n_a, n_b, n_c$ (保证其和为 $n$)的 $3$ 份的方案,满足各份中的数的和 $s_a, s_b, s_c$ 可以构成三角形的三边(不允许三个顶点共线)。
输入格式
一行 $t$ 表示数据组数;接着每组数据中:
- 第 1 行:$n, n_a, n_b, n_c$
- 第 2 行:$x_1, x_2, \dots, x_n$
$t\leq 10^5,\quad \sum n\leq 2\times 10^5, \quad n_a, n_b, n_c\geq 1,\quad x_i \leq 10^9$
输出格式
对每组数据,如果不存在方案,输出 $\texttt{NO}$;否则输出一行 $\texttt{YES}$ 以及:
- 下一行:分在一组内的 $n_a$ 个整数;
- 下一行:分在一组内的 $n_b$ 个整数;
- 下一行:分在一组内的 $n_c$ 个整数。
说明/提示
In the first test case, we can put two $ 1 $ s into each group: the sum in each group would be $ 2 $ , and there exists a triangle with positive area and sides $ 2 $ , $ 2 $ , $ 2 $ .
In the second and third test cases, it can be shown that there is no such way to split numbers into groups.
In the fourth test case, we can put number $ 16 $ into the first group, with sum $ 16 $ , numbers $ 12 $ and $ 1 $ into the second group, with sum $ 13 $ , and the remaining five $ 1 $ s into the third group, with sum $ 5 $ , as there exists a triangle with positive area and sides $ 16, 13, 5 $ .