Breaking Stones

解説

重さ $A_i$ の石をすべて重さ $K$ 以下にするためには、最終的に少なくとも $\left\lceil \frac{A_i}{K}\right\rceil$ 個の石が必要である。

また、石を $1$ 回砕くと石の個数は $1$ 個増えるため、必要な操作回数の最小値は

$$\left\lceil \frac{A_i}{K}\right\rceil-1=\left\lfloor\frac{A_i-1}{K}\right\rfloor$$

であり、求める答えは

$$\sum_{i=1}^{N}\left\lfloor\frac{A_i-1}{K}\right\rfloor$$

である。これを計算することで $O(N)$ でこの問題を解くことができる。