Codeforces Round #642 (Div. 3) B. Two Arrays And Swaps
B. Two Arrays And Swaps
time limit per test1 second
memory limit per test256 megabytes
inputstandard input
outputstandard output
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≤i,j≤n) and swap ai and bj (i.e. ai becomes bj and vice versa). Note that i and j can be equal or different (in particular, swap a2 with b2 or swap a3 and b9 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≤t≤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≤n≤30;0≤k≤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 a1,a2,…,an (1≤ai≤30), where ai is the i-th element of a. The third line of the test case contains n integers b1,b2,…,bn (1≤bi≤30), where bi 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.
Example
inputCopy
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
outputCopy
6
27
39
11
17
Note
In the first test case of the example, you can swap a1=1 and b2=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 a1=1 and b1=10, a3=3 and b3=10 and a2=2 and b4=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].
给定两个等长的数组a[ ], b[ ], 可以执行K次交换,每次选择a[ ]的一个数字和b[ ]的一个数字交换,问K次交换后a[ ]的求和是多少
贪心,对a和b排个序,每次用a[ ]最小的和b[ ]最大的交换,最后求和
//#define debug
#ifdef debug
#include <time.h>
#include "/home/majiao/mb.h"
#endif
#include <iostream>
#include <algorithm>
#include <vector>
#include <string.h>
#include <map>
#include <set>
#include <math.h>
#include <stack>
#include <queue>
#define MAXN (64)
#define ll long long int
#define QAQ (0)
using namespace std;
int n, m;
int a[MAXN], b[MAXN];
int main() {
#ifdef debug
freopen("test", "r", stdin);
clock_t stime = clock();
#endif
int Q;
scanf("%d ", &Q);
while(Q--) {
int K;
scanf("%d %d ", &n, &K);
for(int i=1; i<=n; i++) scanf("%d ", a+i);
for(int i=1; i<=n; i++) scanf("%d ", b+i);
sort(a+1, a+1+n);
sort(b+1, b+1+n, greater<int>());
int i = 1;
for(int j=1; i<=K&&j<=n; j++)
if(a[i] < b[i]) swap(a[i], b[i]), i ++;
int sum = 0;
for(int i=1; i<=n; i++) sum += a[i];
printf("%d\n", sum);
}
#ifdef debug
clock_t etime = clock();
printf("rum time: %lf 秒\n",(double) (etime-stime)/CLOCKS_PER_SEC);
#endif
return 0;
}
