Convex Array - 题目

你得到一个长度为 $n$ 的整数数组 $a$。

判断是否存在一个它的排列 $b$，使得对于每个 $2\leq i \leq n-1$，都有 $b_{i-1} + b_{i+1} \ge 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$。

对于每组输入数据，输出一行 YES，如果存在满足要求的排列；否则输出 NO。

10
4
0 3 4 6
4
5 4 1 4
8
1 4 4 8 6 10 10 4
7
2 1 5 1 9 4 6
6
7 1 6 10 2 3
7
6 6 10 2 5 3 8
4
9 9 1 5
4
8 4 3 4
7
1 2 1 6 4 2 9
7
3 9 7 5 9 10 10

YES
NO
NO
YES
YES
NO
YES
YES
YES
NO

在第一个例子中的第一组输入数据中，数组 $[0, 3, 4, 6]\$ 满足条件的排列是 $[4, 0, 3, 6]$ 和 $[6, 3, 0, 4]$。

设 $S$ 是单个测试中所有输入数据组的 $n$ 之和。

QOJ.ac