きままにものづくり

日々の気付いたことなんかを書いてます。

SRM605Div1Easy

問題

味と型があるハンバーガーがN個渡される。満足度Sはハンバーガーの型の種類Yと味の総量Tを用いてS=Y*Tと表される。ハンバーガーが与えられた時の最大の満足度を求めよ。

解法

型ごとの味の総和の最大値を計算し、味により降順にソートする。型をひとつ追加するごとに、満足度を計算し、最大値なら更新していく。

計算量

 O(N)

コード