文系ギャルが0から始める競技プログラミング#25

Intro

この記事は不定期連載です。
↓最初の一本はこちら↓
文系ギャルが0から始める競技プログラミング#0

↓直前の記事はこちら↓
文系ギャルが0から始める競技プログラミング#24

・ABC121C ー 魔剤

今日も調子に乗ってC問題解いていきます！！！！！
典型だしオススメだよーって問題あったら、ぜひ教えてほしいです！！！

天才競プロerの選ぶ「この問題解いとけ100選」みたいなのないの？？？

— マリー (@CBOX360) May 9, 2019

そういえば先日Kindleでチーター本をついに買いまして、土日でなんとなく読んでます。
コレ最初に読むべきだったなあと猛省した…。
必携アイテム系の中で一番初心者向けかも。

最強最速アルゴリズマー養成講座　プログラミングコンテストTopCoder攻略ガイド

っさて、解いていきましょ〜〜〜！

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

制約
入力は全て整数である。
1≤N,M≤10^5
1≤Ai≤10^9
1≤Bi≤10^5
B1+...+BN≥M

入力
入力は以下の形式で標準入力から与えられる。
N M
A1B1
A2B2
⋮
ANBN

出力
M本の栄養ドリンクを買い集めるのに必要な最小の金額を出力せよ。

C - Energy Drink Collector

エナドリでレート上がるなら今頃やばいことになってるな・・・
モンスター白を一日2〜3本飲んでて、家計を魔剤代が圧迫しています笑

それはさておき、ゴールを整理しましょう！
一番安く、魔剤を欲しいだけ買うことです。
N軒あるお店にはそれぞれ在庫数と値段が決まっていて、
安い順に買いまわらなきゃいけないということがわかりました。

なんとか並べ替えたい、安い順に。
それが！！！pairというものを使えば実現できるらしいです！！！

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

安い順に並べることはできました。
あとは実際に買っていくとして、どうやってM本で止めるかを考えます。。。

変数honsuuを作り(韻がすごい)、本数をカウントします。
バシバシ掛け算してぶっこみつつ、ほしいM本をオーバーしたら止めて、オーバーした分を引く戦法を思いつきました。

 long long honsuu = 0,ans = 0;
   int i=0;
   for(i=0;honsuu<M;i++){
       ans += arr[i].first * arr[i].second;
       honsuu += arr[i].second;
   }
   if(honsuu-M>0){
       ans -= (honsuu - M)*arr[i-1].first;
   }
   cout << ans << endl;

  ほしい本数で止めるのではなくて、ぶっこんで引く形になってしまいましたが想定通り動いてはいそう？
なので、コレでよしとします。優勝！

#include <iostream>
#include <algorithm>
#include <string>
#include <cmath>
#include <vector>
#include <regex>
#include <map>
#include <set>
using namespace std;
int main(){
   int N,M;
   cin >> N >> M;
   
   vector<pair<long long,long long>> arr(N);
   for(int i=0;i<N;i++){
       cin >> arr[i].first >> arr[i].second;
   }
   sort(arr.begin(),arr.end());
   
   long long honsuu = 0,ans = 0;
   
   int i=0;
   for(i=0;honsuu<M;i++){
       ans += arr[i].first * arr[i].second;
       honsuu += arr[i].second;
   }
   
   if(honsuu-M>0){
       ans -= (honsuu - M)*arr[i-1].first;
   }
   cout << ans << endl;
   return 0;
}

優勝〜〜〜〜〜〜〜〜〜〜！
こういうのさっくり思いつく人超かっこいいですね…。
修行します…より天才ムーブを取れるように……

Outro

#26に続く！(不定期連載です。)

これは成功と挫折を繰り返し、
タピオカ片手に難問を解く、
ギャルプログラマが生まれるまでの物語である…。