ABC313_C – Approximate Equalization 2

問題
提出
1. 解けた

問題

C - Approximate Equalization 2

AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.

提出

Submission #44835466 - AtCoder Beginner Contest 313

AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.

解けた

操作では$sum(A_i)$の値は変わらない。
また、最小値と最大値の差を1以下にするには、最大値を$\lfloor sum(A_i)/N \rfloor$にする必要がある。
操作後の配列の最大値を$t$、その個数を$x$とすると、以下の式が成り立つ。
$$sum(A_i)=tx+(t-1)(N-x)$$
この式から個数$x$がもとまる。
$$x=sum(A_i)+N-N*t$$

操作後の配列は$t-1$が$N-x$個、$t$が$x$個になる。
$A_i$の小さい方から$t-1$にするのが最適になるので、$A_i$をソートして、操作後の配列との差を計算する。
操作1回あたり値を2つ変化させることができるので、求めた差の半分が答えになる。