hotpepsiの練習帳

SRM 605

greedy, ソート | 02:36

Div1 Easy (250) AlienAndHamburgers

問題

• エイリアンのFredは地球を滅ぼす前にハンバーガーを食べておくことにした
• 種類とおいしさの配列が与えられる
• 満足度は種類の数×おいしさの合計である
• 満足度の最大値を求める

方針

• 貪欲っぽい
• (種類,おいしさの降順)でソート
• ひとつずつ見ていき、同じ種類かつおいしさが正ならまとめる
• まとめたあと、おいしさでソート
• おいしさが正なら必ず増加する
• おいしさが負で、総量が増加しないなら、次のを食べても増加することはない
• おいしい順に食べて、食べても増えないならやめる
• Passed System Test
• https://github.com/firewood/topcoder/blob/master/srm_6xx/srm_605/AlienAndHamburgers.cpp

結果

o-- 180.04pt 303rd/658 rating 1228 -> 1294 (+66)

ちゃんと解けた。

http://togetter.com/li/618981