2012JOI予選C 最高のピザ 解説
解説
まず、トッピングの個数を固定することを考えます。トッピングの個数が一定なら、カロリーを高いものから貪欲に選んでいくのが当然最適です。
そこで、トッピングの個数を決め打ちして最大の1ドルあたりのカロリー数を計算し、最大のものをとればよいです。
また、余談ですが、トッピングごとに値段が異なっても、この問題は解くことができます。考えてみましょう。
まず、トッピングの個数を固定することを考えます。トッピングの個数が一定なら、カロリーを高いものから貪欲に選んでいくのが当然最適です。
そこで、トッピングの個数を決め打ちして最大の1ドルあたりのカロリー数を計算し、最大のものをとればよいです。
また、余談ですが、トッピングごとに値段が異なっても、この問題は解くことができます。考えてみましょう。