Colorful T-Shirts [第八回 アルゴリズム実技検定 E]

https://atcoder.jp/contests/past202109-open/tasks/past202109_e

解説

https://atcoder.jp/contests/past202109-open/submissions/26602632

貪欲法で解いていく。
かかる値段を最小化したいと考えた場合、簡単な方針として、安いものから選択するという方針がある。
今回はこれで解いていこう。

安いものから選択する

具体的に方針を示すと、全てのTシャツを価格が安い順に並び替えて、買うかどうかを判定していく。
まだ買ってない色のTシャツなら購入して、そうでないなら買わないという感じで購入していき、
K枚買ったら終了。

実装について

自分のC++の実装では、pairとソートをうまく使って、順番に処理している。
pairの配列に対して昇順ソートを適用すると、第一要素で昇順にして、第一要素が同じなら第二要素で昇順にしてくれる。
今回はpairの第一要素に値段をおいてソートを行う。
第二要素はソート的には使っていない（別にどんな順番でもいい）のだが、
色を保持しておくことでソートしても対応する色を楽に取ってくることができる。
この辺は好き好きで実装するといい。

あと、購入済みの色を管理するためにsetを利用している。

int N, K;
int c[101010], p[101010];
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N >> K;
    rep(i, 0, N) cin >> c[i];
    rep(i, 0, N) cin >> p[i];

    vector<pair<int, int>> orders;
    rep(i, 0, N) orders.push_back({ p[i], c[i] });
    sort(all(orders));

    set<int> used;
    ll ans = 0;
    rep(i, 0, N) {
        int price = orders[i].first;
        int color = orders[i].second;

        if (used.count(color)) continue;

        ans += price;
        used.insert(color);

        if (used.size() == K) {
            cout << ans << endl;
            return;
        }
    }

    cout << -1 << endl;
}