問題
https://codeforces.com/contest/1353/problem/B (新しいタブで開く)
問題文
長さ の自然数列 と、整数 が与えられる。
1 回の操作で、index を選び、 を swap させることができる。
最大 回の操作をしたとき、 の総和の最大値は?
制約
サンプル
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
考察
の小さい要素と の大きい要素を入れ替えるようにすればよさそう。
まず は昇順、 は降順にソートしておく。
そしたら 先頭から 個を、 なら 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; }