← 返回题目列表

Codeforces · 1189/B

B. 数字圈

中文机器翻译题面 查看原题

给你 $$$n$$$ 数字 $$$a_1, a_2, \ldots, a_n$$$。是否有可能将它们排列成一个圆圈,使得每个数字都严格小于其邻居的总和?

例如,对于数组$$$[1, 4, 5, 6, 7, 8]$$$,左边的排列有效,右边的排列无效,如$$$5\ge 4 + 1$$$和$$$8> 1 + 6$$$。

输入

第一行包含一个整数 $$$n$$$ ($$$3\le n \le 10^5$$$) — 数字的数量。

第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \leq a_i \le 10^9$$$) — 数字。给定的数字不一定不同(即允许重复)。

输出

如果无解,则在第一行输出“NO”。

如果有解决方案,则在第一行输出“YES”。在第二行中输出 $$$n$$$ 个数字 — 数组中的元素按照它们在圆中停留的顺序排列。您输出的第一个和最后一个元素被视为圆中的邻居。如果有多个解,输出任意一个。您可以打印以任何元素开头的圆圈。

示例

输入 #1

3
2 4 3

输出 #1

YES
4 2 3

输入 #2

5
1 2 3 4 4

输出 #2

YES
4 4 2 1 3

输入 #3

3
13 8 5

输出 #3

NO

输入#4

4
1 10 100 1000

输出#4

NO

注意

第一个示例中显示了一种可能的安排:

$$$4< 2 + 3$$$;

$$$2 < 4 + 3$$$;

$$$3< 4 + 2$$$.

第二个示例中显示了一种可能的布置。

在第三个示例中,无论我们如何将 $$$13, 8, 5$$$ 排列成一个圆圈,$$$13$$$ 都会以 $$$8$$$ 和 $$$5$$$ 作为邻居,但 $$$13\ge 8 + 5$$$。

第四个例子没有解决方案。