P12546 [UOI 2025] Convex Array

给定一个长度为 $n$ 的整数数组 $a$。 判断是否存在一种元素排列 $b$，使得对于每个 $2 \leq i \leq n-1$，都满足条件 $b_{i-1} + b_{i+1} \geq 2 \cdot b_i$。 本题中，每个测试点包含多组输入数据。你需要对每组数据独立求解。

第一行包含一个整数 $T$ $(1 \le T \le 10^5)$ —— 输入数据的组数。接下来是各组数据的描述。 每组数据的第一行包含一个整数 $n$ $(3 \le n \le 3 \cdot 10^5)$ —— 数组 $a$ 的长度。 每组数据的第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$ $(0 \le a_i \le 10^9)$ —— 数组 $a$ 的元素。 保证单个测试点中所有输入数据的 $n$ 之和不超过 $3 \cdot 10^5$。

对于每组输入数据，如果存在满足条件的排列，输出一行 $\tt{YES}$，否则输出 $\tt{NO}$。

在第一个样例的第一组输入数据中，数组 $[0, 3, 4, 6]$ 的满足条件的排列包括 $[4, 0, 3, 6]$ 和 $[6, 3, 0, 4]$。 ### 评分标准 设 $S$ 为单个测试点中所有输入数据的 $n$ 之和。 - （$3$ 分）：$n = 4$； - （$4$ 分）：$T = 1$，$n \le 7$； - （$7$ 分）：$T = 1$，$n \le 15$； - （$5$ 分）：如果存在满足条件的排列，则存在一种满足条件的排列满足 $b_1 \ge b_2$ 且 $b_2 \le b_3$； - （$17$ 分）：$S \le 50$； - （$10$ 分）：$S \le 400$； - （$13$ 分）：$S \le 2000$； - （$9$ 分）：$S \le 8000$； - （$18$ 分）：对于所有 $1 \le i \le n$，$a_i \le 10^6$； - （$14$ 分）：无额外限制。 翻译由 DeepSeek V3 完成