Very Different Array (Codeforces 1921D)
Tags: Greedy, two pointers

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.

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

Output: For each test case, output a single integer — the maximum total difference $$$D$$$ that can be obtained.

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

Sample Inputs:
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

Sample Outputs:
16
0
12
11
10
23
15
25
7

Solution (Python):
import sys
import math

def readline():
    return sys.stdin.readline().strip()
inputArray = lambda : list(map(int, input().split()))
inputString = lambda : list(input().split())

def tc(solve):
    for _ in range(int(readline())):
        solve()

@tc
def solve():
    (n, m) = inputArray()
    a = inputArray()
    b = inputArray()
    a.sort()
    b.sort()
    b = b[::-1]
    i = 0
    j = 0
    k = m - 1
    sumx = 0
    l = 0
    r = n - 1
    while l <= r:
        y = abs(b[j] - a[l])
        z = abs(b[k] - a[r])
        if y > z:
            sumx += y
            j += 1
            l += 1
        else:
            sumx += z
            k -= 1
            r -= 1
    print(sumx)

Solution (Python):
def case():
    (n, m) = ints()
    a = ints()
    b = ints()
    a.sort()
    b.sort(reverse=True)
    l = 0
    r = -1
    diff = 0
    for _ in range(n):
        dl = abs(b[l] - a[l])
        dr = abs(b[r] - a[r])
        if dl > dr:
            diff += dl
            l += 1
        else:
            diff += dr
            r -= 1
    return diff

def main():
    for _ in range(int(input())):
        print(case())

def ints():
    return list(map(int, input().split()))

def floats():
    return list(map(float, input().split()))
if __name__ == '__main__':
    main()

Solution (Python):
def solve():
    (l_a, l_b) = map(int, input().split())
    a = list(map(int, input().split()))
    b = list(map(int, input().split()))
    a.sort()
    b.sort()
    (left_a, left_b) = (0, 0)
    (right_a, right_b) = (len(a) - 1, len(b) - 1)
    s = 0
    for i in range(len(a)):
        diff1 = abs(b[right_b] - a[left_a])
        diff2 = abs(a[right_a] - b[left_b])
        if diff1 > diff2:
            s += diff1
            right_b -= 1
            left_a += 1
        else:
            s += diff2
            left_b += 1
            right_a -= 1
    return s
num_of_input = int(input())
for _ in range(num_of_input):
    print(solve())