AtCoder 313C - Approximate Equalization 2

https://atcoder.jp/contests/abc313/tasks/abc313_c

C - Approximate Equalization 2

본 글은 에디토리얼을 해석하고 제 해석대로 간단하게 나타낸 글입니다.

 

먼저, $A_i$를 주어진 수열, $B_i$를 $A_i$를 조작해서 얻어야 하는 목표 수열이라고 합시다.

 

먼저, $A=B$가 되는 최소의 조작횟수를 구하는 방법을 살펴봅시다.

 

위의 식의 값을 $S$라고 합시다.

 

$A_i, A_j$를 조작해서 얻을 수 있는 $S$의 변화량은 다음과 같습니다.

- $A_i$를 $+1$, $A_j$를 $-1$.

- $A_i$를 $-1$, $A_j$를 $+1$.

두 가지 경우에 대해서 $S$의 변화량을 살펴보겠습니다.

 

- $A_i$를 $+1$, $A_j$를 $-1$.

$A_i > B_i$, $A_j > B_j$인 경우, $dS=0$.

$A_i > B_i$, $A_j < B_j$인 경우,  $dS=2$.

$A_i < B_i$, $A_j > B_j$인 경우, $dS=-2$.

$A_i < B_i$, $A_j < B_j$인 경우, $dS=0$.

 

- $A_i$를 $-1$, $A_j$를 $+1$.

$A_i > B_i$, $A_j > B_j$인 경우, $dS=0$.

$A_i > B_i$, $A_j < B_j$인 경우,  $dS=-2$.

$A_i < B_i$, $A_j > B_j$인 경우, $dS=2$.

$A_i < B_i$, $A_j < B_j$인 경우, $dS=0$.

 

우리는 $S=0$으로 만들어야 하므로 $dS=-2$인 경우만을 보아야 합니다.

 

한 번의 조작으로 $dS=-2$의 결과를 얻으므로, 조작에 필요한 횟수는 $\frac{S}{2}$가 성립합니다.

 

이제 문제인 $i \neq j \Rightarrow |B_i-B_j| \leq 1$일때의 $A$를 조작하는 최소횟수를 구해봅시다.

위의 식을 만족하는 $B$를 생각해보자면, $k, k, k, ..., k$꼴이거나, $k, k, k, ..., k+1, k+1$등의 꼴이어야합니다.

 

$k$를 구하는 방법은 아주 간단합니다.

$\sum_{i=1}^{N} A_i = S$라고 할때,

$\sum_{i=1}^{N} B_i = \left \lfloor \frac{S}{N} \right \rfloor \times N + r=S$ $(0 \leq r < N)$을 만족해야하며, $r=1+1+...+1$을 $B$에 적절하게 분배해야하므로 $k=\left \lfloor \frac{S}{N} \right \rfloor$입니다.

적절하게 분배하는 방법은 $i < j \Rightarrow A_i < A_j$로 정렬 후,

$B_1, B_2, ..., B_{N-r} = \left \lfloor \frac{S}{N} \right \rfloor$

$B_{N-r+1}, ..., B_N = \left \lfloor \frac{S}{N} \right \rfloor + 1$로 두면 최적해를 구할 수 있습니다.

이제, $\sum_{i=1}^{N} |A_i-B_i|$구하고 $2$로 나누어주면 됩니다. ($A$를 $B$로 일치시키는 방법에서 소개했음)