2012JOI予選C 最高のピザ 解説

問題リンク

解説

まず、トッピングの個数を固定することを考えます。トッピングの個数が一定なら、カロリーを高いものから貪欲に選んでいくのが当然最適です。

そこで、トッピングの個数を決め打ちして最大の1ドルあたりのカロリー数を計算し、最大のものをとればよいです。

また、余談ですが、トッピングごとに値段が異なっても、この問題は解くことができます。考えてみましょう。