B. Two Arrays And Swaps (Codeforces Round #642 Div. 3)

問題

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

問題概要

長さnの正の整数で構成された配列aとbが与えられる。また、正の整数kも与えられる。（ただしk<=n）

aとbの項目をk回以下入れ替えて作れる配列aのうち、各項の合計が最大になるときの最大値を答えよ。

考察

まず、aの項のうち大きいものからn-k個については動かす必要がありません。

また、k回「以下」というのがポイントで、マイナスになるような操作はしなくてもいいということになります。なので、aの残りk個と、bのn個のうちから大きいものをk個取る、としてよいです。

#include <bits/stdc++.h>
using namespace std;
 
int main() {
    int t;
    cin >> t;
    while (t--) {
        int n, k;
        cin >> n >> k;
        vector<int> a(n);
        vector<int> b(n);
        for (int i = 0; i < n; i++) cin >> a[i];
        for (int i = 0; i < n; i++) cin >> b[i];
        sort(a.rbegin(), a.rend());
        int ans = 0;
        for (int i = 0; i < n - k; i++) ans += a[i];
        for (int i = n - k; i < n; i++) b.emplace_back(a[i]);
        sort(b.rbegin(), b.rend());
        for (int i = 0; i < k; i++) ans += b[i];
        cout << ans << endl;
    }
}

反省など

他の人の実装を見てみると、もっと効率よく書けるようです。自分の実装は、第一印象で浮かんだものをそのまま書き下したような感じなので、あまり煮詰まっているとは言えませんね。

このレベルの問題だとそれでもすぐ通せるのでよいのですが、もう少し難易度が上がってくると破綻しがちです。なので、考察をもう少し詰めるとか実装に対する設計をちゃんとするとかしたほうがよいです。