Hatena::Grouptopcoder

hotpepsiの練習帳

2014-04-11

SRM 605

| 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

ゲスト



トラックバック - http://topcoder.g.hatena.ne.jp/firewood/20140411