2014-09-27
SRM 634
Div1 Easy (250) ShoppingSurveyDiv1
問題
- M種類の商品があり、購入総数が配列で与えられる
- N人の顧客がいて、それぞれの種類の商品を最大1個買う
- K種類以上購入した顧客(big shopper)の最小値を求める
方針
- とりあえず均等に振り分ける
- と、サンプルが通らない
- big shopperには買えるだけ買わせるのがベストで、残りを均等に分配する
- big shopperが何人かわからないので、2分探索
- Passed System Test
- ソートしないなら全探索でよかった
- https://github.com/firewood/topcoder/blob/master/srm_6xx/srm_634/ShoppingSurveyDiv1.cpp
結果
o-- 139.27pt 185th/394 rating 1712 -> 1705 (-7)
ださいコードだけど、毎回ソートして全探索でTLEしている人もいたので、結果的にはまあ良かった。
最大ケースを用意しておくべき。
コメントを書く
トラックバック - https://topcoder-g-hatena-ne-jp.jag-icpc.org/firewood/20140927