1921D.md (2246B)
1 Source: https://codeforces.com/problemset/problem/1921/D 2 3 D. Very Different Array 4 5 time limit per test 6 7 2 seconds 8 9 memory limit per test 10 11 256 megabytes 12 13 input 14 15 standard input 16 17 output 18 19 standard output 20 21 Petya has an array $a_i$ of $n$ integers. His brother Vasya became envious and decided to make his own array of $n$ integers. 22 23 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$. 24 25 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. 26 27 Help Vasya find the maximum difference $D$ he can obtain. 28 29 Input 30 31 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. 32 33 The first line of each test case contains two integers $n$ and $m$ ($1\le n\le m\le 2 \cdot 10^5$). 34 35 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$). 36 37 It is guaranteed that in a test, the sum of $m$ over all test cases does not exceed $2 \cdot 10^5$. 38 39 Output 40 41 For each test case, output a single integer — the maximum total difference $D$ that can be obtained. 42 43 Example 44 45 Input 46 47 ``` 48 9 49 50 4 6 51 52 6 1 2 4 53 54 3 5 1 7 2 3 55 56 3 4 57 58 1 1 1 59 60 1 1 1 1 61 62 5 5 63 64 1 2 3 4 5 65 66 1 2 3 4 5 67 68 2 6 69 70 5 8 71 72 8 7 5 8 2 10 73 74 2 2 75 76 4 1 77 78 9 6 79 80 4 6 81 82 8 10 6 4 83 84 3 10 6 1 8 9 85 86 3 5 87 88 6 5 2 89 90 1 7 9 7 2 91 92 5 5 93 94 9 10 6 3 7 95 96 5 9 2 3 9 97 98 1 6 99 100 3 101 102 2 7 10 1 1 5 103 ``` 104 105 Output 106 107 ``` 108 16 109 0 110 12 111 11 112 10 113 23 114 15 115 25 116 7 117 ``` 118 119 Note 120 121 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$. 122 123 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$. 124 125 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$.