AtCoder ABC 121 C - Energy Drink Collector (灰色, 300 点)

これでひとまず ABC 100 以降の CD 問題は全部書けた

問題へのリンク

問題概要

個のお店があって、各店 では 1 本 円のエナジードリンクを 本まで買うことができる。

全部で 本のドリンクを買いたい。最小で何円で実現できるか？

制約

• 

考えたこと

基本的に安いお店から優先的に買いたい。よって 個のペア

• 
• 
• ...
• 

を の値が小さい順にソートして、その順番にお店を回っていき、 本に達するまで順番に買っていく。

ここでペアをソートするのは、C++ では std::pair が便利に使える。今回の場合は比較演算子を指定することなくデフォルトの比較演算子 (辞書順比較) で問題ない。

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

using pll = pair<long long, long long>;
int main() {
    int N;
    long long M;
    cin >> N >> M;
    vector<pll> v(N);
    for (int i = 0; i < N; ++i) cin >> v[i].first >> v[i].second;
    sort(v.begin(), v.end());

    long long res = 0;
    for (int i = 0; i < N && M > 0; ++i) {
        res += v[i].first * min(M, v[i].second);
        M -= min(M, v[i].second);
    }
    cout << res << endl;
}