きままにものづくり

日々の気付いたことなんかを書いてます。

SRM634Div1Easy

問題

M個の品物がありN人の買い物客がいる。一人につきひとつまでしか商品を買えない。K個以上の品物を購入した者を大口顧客と定義する。どの品物がいくつ購入されたかを示す数列が与えられる。この条件を満たす最小の大口顧客を求めよ。

解法

大口顧客の数を変数とし、条件を満たすかを全探索する。大口顧客の数を最小にするためには、普通の客はK-1個の品物を買い、大口顧客は全ての商品を買うようにする。
以下の式を満たす時、条件を満たす。
 \{n \geq X\} \land \{n(K-1) \geq S\}
ただし、nは普通顧客数、Xは大口顧客の数を引いた後の品物購入数の最大値、Sは品物購入数の総量を示す。nがXより大きいのなら一人の普通顧客がひとつの商品を複数個購入する必要がないので総量の比較だけで条件を満たすかを確認できる。
二分探索を使えば、より高速化できるが線形探索でも十分である。

計算量

O(NM)

コード