AtCoder Beginner Contest 127 D - Integer Cards
問題概要
N枚のカードがある。カードを入力で指定される可能な枚数まで指定された値に書き換えられる。和の最大値はいくらか。
解法
問題で行う操作を考えてみると、場にあるカードと入力で与えられるカード全てを混ぜ合わせたカード群の中から数値が大きい順にN枚取ってくるという操作に言い換えられる。本番中にこれは気づけた。(しかしなんかバグった。かなしい。)
よって、vector<pair<long long,long long>>に入力されるデータを<カードに書かれている数値,枚数>という形で突っ込んであげてsortして数えるだけ。
これを実装して、AC。多分ソートがネックなのでO(NlogN)。
