C++ pairを用いてABC121 C問題を解く

競技プログラミングの備忘録用
今回はSTLコンテナpairとvectorを組み合わせてABC121 C問題を解く．

C - Energy Drink Collector

問題

栄養ドリンクにレーティング上昇効果があると聞いた高橋くんは、$M$本の栄養ドリンクを買い集めることにしました。栄養ドリンクが売られている店は $N$軒あり、
$i$軒目の店では1本$A_i$円の栄養ドリンクを $B_i$本まで買うことができます。
最小で何円あれば $M$本の栄養ドリンクを買い集めることができるでしょうか。
なお、与えられる入力では、十分なお金があれば $M$本の栄養ドリンクを買い集められることが保証されます。

制約

入力は全て整数である。

• $1≤N,M≤10^5$
• $1≤A_i≤10^9$
• $1≤B_i≤10^5$
• $B_1+...+B_N≥M$

方針

pair型のvectorを宣言し，pairの第一要素を値段とし，第二要素を個数をする．
第一要素を基準にソートすることで値段が安い順に個数を並べる．
あとは値段が安いものから順番に購入した数が$M$個になるまで値段を加えていく．

pair型vectorの宣言

vector<pair<long long, long long> A(N);

第一要素と第二要素にlong long型を持つ$N$個のpair型のvectorを宣言

N個のvectorに値を入力

for(int i=0; i<N; i++){
    cin >> A.at(i).first >> A.at(i).second;
}

pairの第一要素を基準にvectorを昇順にソートする

sort(A.begin(), A.end())

解法コード

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main()
{
    int N, M;
    cin >> N >> M;
    vector<pair<ll, ll>> A(N);
    for(int i=0; i<N; i++){
        cin >> A.at(i).first >> A.at(i).second;
    }
    sort(A.begin(), A.end());
    int rest=M;
    ll money=0;
    for(int i=0; i<N; i++){
        if(A.at(i).second>rest){
            money+=rest*A.at(i).first;
            break;
        }
        else{
            money+=A.at(i).second*A.at(i).first;
            rest-=A.at(i).second;
        }
    }
    cout << money << endl;
}