← 返回题目列表

Codeforces · 1843/A

A. Sasha 和数组着色

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

Sasha 找到了一个由 $$$n$$$ 整数组成的数组 $$$a$$$,并要求你绘制元素。

您必须绘制数组的每个元素。您可以根据需要使用任意多种颜色,但每个元素都应该恰好绘制为一种颜色,并且对于每种颜色,应该至少有一个该颜色的元素。

一种颜色的成本是 $$$\max(S) - \min(S)$$$ 的值,其中 $$$S$$$ 是该颜色的元素序列。整个着色的成本是所有颜色的成本之和。

例如,假设您有一个数组 $$$a = [\color{red}{1}, \color{red}{5}, \color{blue}{6}, \color{blue}{3}, \color{red}{4}]$$$,并且您将其元素绘制为两种颜色,如下所示:位置 $$$1$$$、$$$2$$$ 和 $$$5$$$ 上的元素的颜色为 $$$1$$$;位置 $$$3$$$ 和 $$$4$$$ 上的元素的颜色为 $$$2$$$。然后:

- 颜色 $$$1$$$ 的成本为 $$$\max([1, 5, 4]) - \min([1, 5, 4]) = 5 - 1 = 4$$$;
- 颜色 $$$2$$$ 的成本为 $$$\max([6, 3]) - \min([6, 3]) = 6 - 3 = 3$$$;
- 着色的总成本为 $$$7$$$。

对于给定的数组 $$$a$$$,您必须计算着色的最大可能成本。

输入

第一行包含一个整数 $$$t$$$ ($$$1 \leq t \leq 1000$$$) — 测试用例的数量。

每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 50$$$) — $$$a$$$ 的长度。

第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \dots, a_n$$$ ($$$1 \leq a_i \leq 50$$$) — 数组 $$$a$$$。

输出

对于每个测试用例,输出最大可能的着色成本。

示例

输入 #1

6
5
1 5 6 3 4
1
5
4
1 6 3 9
6
1 13 9 3 7 2
4
2 2 2 2
5
4 5 2 2 3

输出 #1

7
0
11
23
0
5

注意

在第一个示例中,最佳着色是 $$$[\color{red}{1}, \color{red}{5}, \color{blue}{6}, \color{blue}{3}, \color{red}{4}]$$$。答案是 $$$(5 - 1) + (6 - 3) = 7$$$。

在第二个示例中,唯一可能的颜色是 $$$[\color{blue}{5}]$$$,其答案是 $$$5 - 5 = 0$$$。

在第三个示例中,最佳着色是 $$$[\color{blue}{1}, \color{red}{6}, \color{red}{3}, \color{blue}{9}]$$$,答案是 $$$(9 - 1) + (6 - 3) = 11$$$。