yukicoder 1391 ±1 Abs Sum
まず最初の重要な考察として, $ f_B(x)は$ x = A_iで必ず最小値をとることがある. これは手元で様々なパターンを試すことにより示せる. よって考え方を少し変え, 各$ A_iについて$ Bをすべて考えたときの$ f_B(x)の最小値を求めることにする. これは少し考えると, $ A_iに近い$ K個を$ B_i = 1とし, それ以外の$ N - K個を$ B_i = -1とするのが最適であるということがわかる. これは区間の形で表せて、差分更新することができる.
また$ A_iの累積和を前計算しておくことで$ f_B(x)の最小値の値も高速に求められる(詳しい式は公式解説参照). 計算量は$ O(N)となる.