CF Round #642 B - Two Arrays And Swaps


Tags:cpcodeforcesdiv3greedysort

問題

https://codeforces.com/contest/1353/problem/B

問題文

長さ nn の自然数列 a,ba, b と、整数 kk が与えられる。

1 回の操作で、index i,ji, j を選び、 ai,bja_i, b_j を swap させることができる。
最大 kk 回の操作をしたとき、 aa の総和の最大値は?

制約

  • 1t2001 \le t \le 200
  • 1n301 \le n \le 30
  • 0kn0 \le k \le n
  • 1ai,bi301 \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

考察

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

まず aa は昇順、 bb は降順にソートしておく。
そしたら 先頭から kk 個を、 ai<bia_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;
}