hotpepsiの練習帳

SRM 634

02:10

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している人もいたので、結果的にはまあ良かった。

最大ケースを用意しておくべき。

http://togetter.com/li/723958