Two Arrays And Swaps (Codeforces 1353B)
Tags: Greedy, sortings

You are given two arrays $$$a$$$ and $$$b$$$ both consisting of $$$n$$$ positive (greater than zero) integers. You are also given an integer $$$k$$$.In one move, you can choose two indices $$$i$$$ and $$$j$$$ ($$$1 \le i, j \le n$$$) and swap $$$a_i$$$ and $$$b_j$$$ (i.e. $$$a_i$$$ becomes $$$b_j$$$ and vice versa). Note that $$$i$$$ and $$$j$$$ can be equal or different (in particular, swap $$$a_2$$$ with $$$b_2$$$ or swap $$$a_3$$$ and $$$b_9$$$ both are acceptable moves).Your task is to find the maximum possible sum you can obtain in the array $$$a$$$ if you can do no more than (i.e. at most) $$$k$$$ such moves (swaps).You have to answer $$$t$$$ independent test cases.

Input: The first line of the input contains one integer $$$t$$$ ($$$1 \le t \le 200$$$) — the number of test cases. Then $$$t$$$ test cases follow.The first line of the test case contains two integers $$$n$$$ and $$$k$$$ ($$$1 \le n \le 30; 0 \le k \le n$$$) — the number of elements in $$$a$$$ and $$$b$$$ and the maximum number of moves you can do. The second line of the test case contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le 30$$$), where $$$a_i$$$ is the $$$i$$$-th element of $$$a$$$. The third line of the test case contains $$$n$$$ integers $$$b_1, b_2, \dots, b_n$$$ ($$$1 \le b_i \le 30$$$), where $$$b_i$$$ is the $$$i$$$-th element of $$$b$$$.

Output: For each test case, print the answer — the maximum possible sum you can obtain in the array $$$a$$$ if you can do no more than (i.e. at most) $$$k$$$ swaps.

Note: In the first test case of the example, you can swap $$$a_1 = 1$$$ and $$$b_2 = 4$$$, so $$$a=[4, 2]$$$ and $$$b=[3, 1]$$$.In the second test case of the example, you don't need to swap anything.In the third test case of the example, you can swap $$$a_1 = 1$$$ and $$$b_1 = 10$$$, $$$a_3 = 3$$$ and $$$b_3 = 10$$$ and $$$a_2 = 2$$$ and $$$b_4 = 10$$$, so $$$a=[10, 10, 10, 4, 5]$$$ and $$$b=[1, 9, 3, 2, 9]$$$.In the fourth test case of the example, you cannot swap anything.In the fifth test case of the example, you can swap arrays $$$a$$$ and $$$b$$$, so $$$a=[4, 4, 5, 4]$$$ and $$$b=[1, 2, 2, 1]$$$.

Sample Inputs:
5
2 1
1 2
3 4
5 5
5 5 6 6 5
1 2 5 4 3
5 3
1 2 3 4 5
10 9 10 10 9
4 0
2 2 4 3
2 4 2 3
4 4
1 2 2 1
4 4 5 4

Sample Outputs:
6
27
39
11
17

Solution (Python):
t = int(input())
for _ in range(t):
    (n, k) = map(int, input().split())
    a = list(map(int, input().split()))
    b = list(map(int, input().split()))
    a.sort()
    b.sort(reverse=True)
    for i in range(n):
        if k > 0 and a[i] < b[i]:
            a[i] = b[i]
            k -= 1
    print(sum(a))

Solution (Python):
for _ in range(int(input())):
    (n, k) = map(int, input().split())
    a = list(map(int, input().split()))
    b = list(map(int, input().split()))
    for i in range(k):
        x = max(b)
        y = min(a)
        if x > y:
            a[a.index(y)] = x
            b[b.index(x)] = y
        else:
            break
    print(sum(a))

Solution (Python):
t = int(input())
while t > 0:
    (n, k) = [int(i) for i in input().split()]
    a = sorted([int(i) for i in input().split()])
    b = sorted([int(i) for i in input().split()])
    (ai, bi) = (0, n - 1)
    while k > 0 and a[ai] < b[bi]:
        (a[ai], b[bi]) = (b[bi], a[ai])
        ai += 1
        bi -= 1
        k -= 1
    print(sum(a), end='\n\n')
    t -= 1