310499: CF1843A. Sasha and Array Coloring
Description
Sasha found an array $a$ consisting of $n$ integers and asked you to paint elements.
You have to paint each element of the array. You can use as many colors as you want, but each element should be painted into exactly one color, and for each color, there should be at least one element of that color.
The cost of one color is the value of $\max(S) - \min(S)$, where $S$ is the sequence of elements of that color. The cost of the whole coloring is the sum of costs over all colors.
For example, suppose you have an array $a = [\color{red}{1}, \color{red}{5}, \color{blue}{6}, \color{blue}{3}, \color{red}{4}]$, and you painted its elements into two colors as follows: elements on positions $1$, $2$ and $5$ have color $1$; elements on positions $3$ and $4$ have color $2$. Then:
- the cost of the color $1$ is $\max([1, 5, 4]) - \min([1, 5, 4]) = 5 - 1 = 4$;
- the cost of the color $2$ is $\max([6, 3]) - \min([6, 3]) = 6 - 3 = 3$;
- the total cost of the coloring is $7$.
For the given array $a$, you have to calculate the maximum possible cost of the coloring.
InputThe first line contains one integer $t$ ($1 \leq t \leq 1000$) — the number of test cases.
The first line of each test case contains a single integer $n$ ($1 \le n \le 50$) — length of $a$.
The second line contains $n$ integers $a_1, a_2, \dots, a_n$ ($1 \leq a_i \leq 50$) — array $a$.
OutputFor each test case output the maximum possible cost of the coloring.
ExampleInput6 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 3Output
7 0 11 23 0 5Note
In the first example one of the optimal coloring is $[\color{red}{1}, \color{red}{5}, \color{blue}{6}, \color{blue}{3}, \color{red}{4}]$. The answer is $(5 - 1) + (6 - 3) = 7$.
In the second example, the only possible coloring is $[\color{blue}{5}]$, for which the answer is $5 - 5 = 0$.
In the third example, the optimal coloring is $[\color{blue}{1}, \color{red}{6}, \color{red}{3}, \color{blue}{9}]$, the answer is $(9 - 1) + (6 - 3) = 11$.
Input
题意翻译
### 简要题意 给定一个长为 $n$ 的序列，你需要把每个元素分别染成一种颜色，颜色的种类数量不限。 每一种颜色的贡献为染成该色的数的极差。你需要最大化所有颜色贡献和，输出这个和。 ### 输入格式 第一行为 $t$ ，表示数据组数。 对于每一组数据第一行为 $n$ 表示序列长度，第二行为一个长为 $n$ 的序列。 ### 输出格式 每组数据输出一行一个数字，表示答案。Output
**题目描述：**
萨莎找到一个由n个整数组成的数组a，并要求你对元素进行着色。你可以使用任意多的颜色，但每个元素应该恰好被涂成一种颜色，并且对于每种颜色，都应至少有一个该颜色的元素。
一种颜色的**成本**是max(S) - min(S)，其中S是该颜色的元素序列。整个着色的**成本**是所有颜色成本的总和。
例如，假设你有数组a = [1, 5, 6, 3, 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 ≤ t ≤ 1000）——测试用例的数量。
每个测试用例的第一行包含一个整数n（1 ≤ n ≤ 50）——数组a的长度。
第二行包含n个整数a_1, a_2, ..., a_n（1 ≤ a_i ≤ 50）——数组a。
**输出格式：**
对于每个测试用例输出着色的最大可能成本。
**示例：**
**输入**
```
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
```
**输出**
```
7
0
11
23
0
5
```
**说明：**
- 在第一个例子中，最优的着色之一是[1, 5, 6, 3, 4]。答案是(5 - 1) + (6 - 3) = 7。
- 在第二个例子中，唯一的可能着色是[5]，其答案是5 - 5 = 0。
- 在第三个例子中，最优着色是[1, 6, 3, 9]，答案是(9 - 1) + (6 - 3) = 11。**萨莎和数组着色** **题目描述：** 萨莎找到一个由n个整数组成的数组a，并要求你对元素进行着色。你可以使用任意多的颜色，但每个元素应该恰好被涂成一种颜色，并且对于每种颜色，都应至少有一个该颜色的元素。 一种颜色的**成本**是max(S) - min(S)，其中S是该颜色的元素序列。整个着色的**成本**是所有颜色成本的总和。 例如，假设你有数组a = [1, 5, 6, 3, 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 ≤ t ≤ 1000）——测试用例的数量。 每个测试用例的第一行包含一个整数n（1 ≤ n ≤ 50）——数组a的长度。 第二行包含n个整数a_1, a_2, ..., a_n（1 ≤ a_i ≤ 50）——数组a。 **输出格式：** 对于每个测试用例输出着色的最大可能成本。 **示例：** **输入** ``` 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 ``` **输出** ``` 7 0 11 23 0 5 ``` **说明：** - 在第一个例子中，最优的着色之一是[1, 5, 6, 3, 4]。答案是(5 - 1) + (6 - 3) = 7。 - 在第二个例子中，唯一的可能着色是[5]，其答案是5 - 5 = 0。 - 在第三个例子中，最优着色是[1, 6, 3, 9]，答案是(9 - 1) + (6 - 3) = 11。