A16373. Very Different Array
编程题
普及/提高-
知识点
题目描述
Petya has an array $a_i$ of $n$ integers. His brother Vasya became envious and decided to make his own array of $n$ integers.
To do this, he found $m$ integers $b_i$ ( $m\ge n$ ), and now he wants to choose some $n$ integers of them and arrange them in a certain order to obtain an array $c_i$ of length $n$ .
To avoid being similar to his brother, Vasya wants to make his array as different as possible from Petya's array. Specifically, he wants the total difference $D = \sum_{i=1}^{n} |a_i - c_i|$ to be as large as possible.
Help Vasya find the maximum difference $D$ he can obtain.
To do this, he found $m$ integers $b_i$ ( $m\ge n$ ), and now he wants to choose some $n$ integers of them and arrange them in a certain order to obtain an array $c_i$ of length $n$ .
To avoid being similar to his brother, Vasya wants to make his array as different as possible from Petya's array. Specifically, he wants the total difference $D = \sum_{i=1}^{n} |a_i - c_i|$ to be as large as possible.
Help Vasya find the maximum difference $D$ he can obtain.
输入格式
Each test consists of multiple test cases. The first line contains a single integer $t$ ( $1 \le t \le 100$ ) — the number of test cases. This is followed by a description of the test cases.
The first line of each test case contains two integers $n$ and $m$ ( $1\le n\le m\le 2 \cdot 10^5$ ).
The second line of each test case contains $n$ integers $a_i$ ( $1\le a_i\le 10^9$ ). The third line of each test case contains $m$ integers $b_i$ ( $1\le b_i\le 10^9$ ).
It is guaranteed that in a test, the sum of $m$ over all test cases does not exceed $2 \cdot 10^5$ .
The first line of each test case contains two integers $n$ and $m$ ( $1\le n\le m\le 2 \cdot 10^5$ ).
The second line of each test case contains $n$ integers $a_i$ ( $1\le a_i\le 10^9$ ). The third line of each test case contains $m$ integers $b_i$ ( $1\le b_i\le 10^9$ ).
It is guaranteed that in a test, the sum of $m$ over all test cases does not exceed $2 \cdot 10^5$ .
输出格式
For each test case, output a single integer — the maximum total difference $D$ that can be obtained.
输入输出样例
输入 #1
9 4 6 6 1 2 4 3 5 1 7 2 3 3 4 1 1 1 1 1 1 1 5 5 1 2 3 4 5 1 2 3 4 5 2 6 5 8 8 7 5 8 2 10 2 2 4 1 9 6 4 6 8 10 6 4 3 10 6 1 8 9 3 5 6 5 2 1 7 9 7 2 5 5 9 10 6 3 7 5 9 2 3 9 1 6 3 2 7 10 1 1 5
输出 #1
16 0 12 11 10 23 15 25 7
说明/提示
In the first example, Vasya can, for example, create the array $(1, 5, 7, 2)$ . Then the total difference will be $D = |6-1|+|1-5|+|2-7|+|4-2| = 5+4+5+2 = 16$ .
In the second example, all the integers available to Vasya are equal to 1, so he can only create the array $(1, 1, 1)$ , for which the difference $D = 0$ .
In the third example, Vasya can, for example, create the array $(5, 4, 3, 2, 1)$ . Then the total difference will be $D = |1-5|+|2-4|+|3-3|+|4-2|+|5-1| = 4+2+0+2+4 = 12$ .
In the second example, all the integers available to Vasya are equal to 1, so he can only create the array $(1, 1, 1)$ , for which the difference $D = 0$ .
In the third example, Vasya can, for example, create the array $(5, 4, 3, 2, 1)$ . Then the total difference will be $D = |1-5|+|2-4|+|3-3|+|4-2|+|5-1| = 4+2+0+2+4 = 12$ .