codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

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$.