B - Two Arrays And Swaps

問題

https://codeforces.com/contest/1353/problem/B (新しいタブで開く)

問題文

長さ $n$ の自然数列 $a, b$ と、整数 $k$ が与えられる。

1 回の操作で、index $i, j$ を選び、 $a_i, b_j$ を swap させることができる。
最大 $k$ 回の操作をしたとき、 $a$ の総和の最大値は？

制約

• $1 \le t \le 200$
• $1 \le n \le 30$
• $0 \le k \le n$
• $1 \le a_i, b_i \le 30$

サンプル

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

6
27
39
11
17

考察

$a$ の小さい要素と $b$ の大きい要素を入れ替えるようにすればよさそう。

まず $a$ は昇順、 $b$ は降順にソートしておく。
そしたら 先頭から $k$ 個を、 $a_i < b_i$ なら swap し続ければいい。

コード

https://codeforces.com/contest/1353/submission/127017221 (新しいタブで開く)

void solve() {
  int n, k;
  cin >> n >> k;
  vector<int> a(n), b(n);
  rep(i, n) cin >> a[i];
  rep(i, n) cin >> b[i];
  sort(a.begin(), a.end());
  sort(b.begin(), b.end(), greater<int>());
  rep(i, k) {
    if (a[i] < b[i]) {
      swap(a[i], b[i]);
    }
  }
  ll sum = 0;
  rep(i, n) sum += a[i];
  cout << sum << endl;
}