B - Two Arrays And Swaps

cpcodeforcesdiv3greedysort

最終更新日

Table of Contents

Loading...

問題

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 の総和の最大値は?

制約

サンプル

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; }