\(f(x)\) の範囲を実数に拡張して、\(f(x)\) の値として考えられる最小の整数を考えても答えは変わりません。\(A\) がソートされていると仮定し、\(K=0\) の場合について考えます。

\(x\) を固定します。\(|A_i-x|\) が \(B_M\) 以下になるような \(i\) として考えられるものの集合は、連続する \(M\) 個の整数の集合であると分かります。

これを一つ固定して、これを \(\{j,j+1,\dots,j+M-1\}\) とします。このとき、\(B_M\) として考えれられる最小値は \(x=\frac{A_{j+M-1}+A_j}{2}\) のときの \(\frac{A_{j+M-1}-A_j}{2}\) であることがわかります。よって、\(f(x)\) の最小値は \(\frac{A_{j+M-1}-A_j}{2}\) の最小値に等しく、これは \(O(N)\) で求められます。連続なので、最小の整数についても全く同様に求められます。

\(K\) が一般の場合について考えます。\(M \leq K\) の場合、答えは \(0\) です。

そうでない場合を考えます。\(K=0\) の場合の \(f(x)\) の求め方を思い出すと、連続する \(M\) 個の整数の集合を選び、大きいほうから \(k\) 個、小さいほうから \(K-k\) 個を適当な値に設定するのが最適です。

\(k\) をどのように設定したとしても、結局のところ、連続する \(M-K\) 個の整数について \(K=0\) の場合と同様の処理をしていることを踏まえると、\(M\) を \(M-K\) として同じ問題を解けば良いです。よって、この問題を \(O(N\log N)\) で解くことが出来ました。