ABC121 C - Energy Drink Collectorをstd::pairを使って解く

C++のSTLにはstd::pairという関数が用意されている。
2つの値の組を表し、使い方も単純で

pair<値1の型, 値2の型> 変数名;

で宣言して

make_pair(値1, 値2);

を使って値を突っ込んでいくだけだ。

いろいろな場面で活用できるのだが、先日AtCoderの過去問を解いているとき、「配列Aをキーとして配列Bをソートする」という場面に遭遇した。
つまり、配列Aを降順(昇順)にソートしたとき、ソート結果に基づいて配列Bも並び替えたい、というものだ。

この「過去問」とは、以下の問題だ。
いくつか解放が考えられるが、今回は上記で示したpair関数を用いて解く。
atcoder.jp
問題を要約すると「ある個数Mのエナジードリンクを手に入れたとき、エナジードリンクの価格の合計の最低値を求めよ」となる。

回答は以下。

#include <bits/stdc++.h>
using namespace std;

int main(){
    int N, M;
    cin >> N >> M;
    vector<long long> A(N), B(N);
    vector<pair<long long, long long>> p(N);
    for(int i = 0; i < N; ++i) {
        cin >> A[i] >> B[i];
        p[i] = make_pair(A[i], B[i]);
    }

    sort(p.begin(), p.end());

    long long cnt = 0;
    long long mon = 0;
    for(int i = 0; i < N; ++i) {
        if(cnt + p[i].second <= M) {
            mon += p[i].first * p[i].second;
            cnt += p[i].second;
        } else if(cnt + p[i].second > M) {
            while(cnt < M) {
                cnt++;
                mon += p[i].first;
            }
        }

        if(cnt == M) {
            break;
        }
    }

    cout << mon << endl;
}

まず、この部分で標準入力を行っているが、同時にpair型配列に受け取った値A, Bを突っ込んでいる。

    vector<long long> A(N), B(N);
    vector<pair<long long, long long>> p(N);
    for(int i = 0; i < N; ++i) {
        cin >> A[i] >> B[i];
        p[i] = make_pair(A[i], B[i]);
    }

その受け取った値を持つpを、Aをキーにソートする。同じくSTLのsortを用いれば良い。

sort(p.begin(), p.end());

あとは0番目から順番に価格を計算し、変数に突っ込んでいけばよい。

300点問題の中では簡単な部類だが、慣れていないと手が止まる。