B - 鏡餅 解説
by
shobonvip
考察1
上から重さの昇順に使うとしてよいです。
なぜなら、 \(a_1,a_2,\cdots, a_i,a_{i+1}, \cdots, a_m\) の順に使用したとき、 \(a_i > a_{i+1}\) なら、これを交換して \(a_1,a_2,\cdots, a_{i+1},a_i, \cdots, a_m\) の順に使用しても OK だからです。これを繰り返すと、ある解があったとき、上から重さ昇順に使う同じサイズの解があり、この考察が成り立ちます。
考察2
上から重さの昇順に見ていき、「現在の合計重み」<「現在見ているお餅の重さ」のときに貪欲に使うことが最適です。
新しく追加するお餅が軽ければ軽いほど、後の選択肢が包含的に広がり、無視することと比べて損をしないからです。
投稿日時:
最終更新:
