← 返回题目列表

Codeforces · 1509/C

C. 体育节

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

学生会正在准备体育祭的接力赛。

理事会由 $$$n$$$ 名成员组成。他们将在比赛中一前一后地奔跑,成员$$$i$$$的速度是$$$s_i$$$。第$$$i$$$阶段的差异$$$d_i$$$是最先跑的$$$i$$$成员之间的最大和最小跑步速度之间的差异。形式上,如果$$$a_i$$$表示参加比赛的第$$$i$$$个成员的速度,则$$$d_i = \max(a_1, a_2, \dots, a_i) - \min(a_1, a_2, \dots, a_i)$$$。

您想要最小化差异的总和 $$$d_1 + d_2 + \dots + d_n$$$。为此,您可以更改成员的运行顺序。可以达到的最小可能金额是多少?

输入

第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 2000$$$) — 学生会成员人数。

第二行包含 $$$n$$$ 整数 $$$s_1, s_2, \dots, s_n$$$ ($$$1 \le s_i \le 10^9$$$) – 成员的跑步速度。

输出

打印单个整数 — 选择成员顺序后 $$$d_1 + d_2 + \dots + d_n$$$ 的最小可能值。

示例

输入 #1

3
3 1 2

输出 #1

3

输入 #2

1
5

输出 #2

0

输入 #3

6
1 6 3 3 6 3

输出 #3

11

输入#4

6
104 943872923 6589 889921234 1000000000 69

输出#4

2833800505

注意

在第一个测试用例中,我们可以选择让第三个成员先运行,然后是第一个成员,最后是第二个成员。因此$$$a_1 = 2$$$,$$$a_2 = 3$$$,$$$a_3 = 1$$$。我们有:

- $$$d_1 = \max(2) - \min(2) = 2 - 2 = 0$$$。
- $$$d_2 = \max(2, 3) - \min(2, 3) = 3 - 2 = 1$$$。
- $$$d_3 = \max(2, 3, 1) - \min(2, 3, 1) = 3 - 1 = 2$$$。

所得总和为 $$$d_1 + d_2 + d_3 = 0 + 1 + 2 = 3$$$。可以看出,不可能达到更小的值。

在第二个测试用例中,唯一可能的重新排列给出 $$$d_1 = 0$$$,因此最小可能结果是 $$$0$$$。