zukaABCをコツコツ解いていきます。
本記事は，管理人の競技プロ精進日記としてログを取ったものです。モチベーションを爆上げするために，積極的にアウトプットしていく作戦です。
これから競技プログラミングを始めようと考えている人や，なんとなく敷居が高いと感じている人の参考になれば嬉しく思います。その他の記事は以下をご覧ください。
目次
本記事の概要
Atcoderで初心者用のコンテストとして開催されているAtcoder Beginner Contest（通称ABC）を解いていくものです。今回はABC121-C「Energy Drink Collector」です。
ポイント
値段の安い方から買えるだけ買っていく貪欲法です。そのために，まずは栄養ドリンクを安い順に並び替える必要があります。c++では，pair<値段, 本数>のvectorを利用してsortすれば<値段, 本数>を値段基準で小さい順に並び替えることができます。sortはpairの第一引数を基準に並び替えてくれるからです。
一番の障壁となりうるのが，「安い方から買えるだけ買っていく」という部分の実装です。今回は，何軒めのお店にいるのかを示すcnt，合計金額を示すans，M本まであと何本買えば良いのか(残差)を示すresの3つの変数を用意することで見通しよく実装することを心がけました。resを用意してMとのminをとる点がポイントです。
おさえるべき内容
目標変数Mと残差変数resを用意してminをとる貪欲法
実装
#include <bits/stdc++.h>
#define _GLIBCXX_DEBUG
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define repi(i, a, b) for (int i = (int)(a); i < (int)(b); i++)
using namespace std;
typedef long long ll;
int main(){
// オーバーフローに注意
ll N, M;
cin >> N >> M;
// pairのvectorを作る
vector<pair<ll, ll>> X(N);
rep(i, N){
cin >> X[i].first >> X[i].second;
}
// ソートして値段が小さい順にpairの順番を並び替える
sort(X.begin(), X.end());
ll cnt = 0;
ll ans = 0;
ll res = M;
// 残差変数が正のとき繰り返す
while (res > 0){
// そのお店で買える分だけ買う
// M本を越さないように残差とのminをとって考える
ans += X[cnt].first * min(res, X[cnt].second);
// 残差更新
res -= X[cnt].second;
// 今いるお店を更新
cnt ++;
}
cout << ans << endl;
}
コメント