Minimum Cost for Equal

コストを最小化するために、なるべく操作 $1$ を行うことを考えます。

$A, B, C$ を並べ替えても一般性を失わないため、以下では昇順に並べられているとします。

$C \leq K$ より、$A, B$ に対して操作 $1$ を $C - B$ 回行うことは可能です。$\\$ これにより、$\\$ $A, B, C$ は$\\$ $A+(C-B), C, C$ となります。

式を見やすくするため、ここで $A + (C - B) = X$ とします。

次に、$X$ とその他の値を揃えるために、以下の操作を行います。

• $X$ と一方の $C$ に対して操作 $1$ を行う
• その後、$X+1$ ともう一方の $C$ に対して操作 $1$ を行う

この操作を $1$ 回行うごとに、$X$ であったものには $2$ だけ加算され、$C$ であったものにはそれぞれ $1$ ずつ加算されます。 つまり、$1$ 回ごとに $1$ ずつ $X$ と他の値との差が小さくなっていくため、この操作を $C - X$ 回行うことにより、全ての値を等しくすることができます。 しかし、$C$ であったものが $K$ を超えることができないため、この操作を行う回数の上限は $K - C$ 回です。

よって、$C - X \leq K - C$ のときは操作 $2$ を行わずにすべての値を等しくすることができますが、 $K - C < C - X$ のとき、$(C - X) - (K - C)$ 回、すなわち、$C-A+B-K$ 回だけ操作 $2$ を行う必要があります。

これをまとめると、必要なコストは $max(0, C-A+B-K)$ となります。