\(B\) は昇順にソートしたものと考えてよいです。以下 \(B_1\le B_2\le\dots\le B_M\) とします。

\(\sum_{i=1}^M \left\vert B_i-C_i\right\vert\) を最小化する \(C\) は \(C_1\le C_2\le\dots\le C_M\) が成り立っているとしてよいです。

\(A\) を昇順にソートして順番に \(B_1,B_2,\dots,B_M\) とのマッチングを考えればよく、以下の動的計画法で解くことができます。 \(A_1\le A_2\le\dots\le A_N\) とします。

\(\mathrm{dp}[i][j]:=\) \(A_1,A_2,\dots,A_i\) まで見て \(B_1,B_2,\dots,B_j\) までマッチングしたときの \(\sum_{k=1}^j \left\vert B_k-C_k\right\vert\) の最小値 と定めます。

初期化は \(\mathrm{dp}[0][0]=0\) 、遷移は \(\mathrm{dp}[i][j]=\min(\mathrm{dp}[i-1][j],\mathrm{dp}[i-1][j-1]+\left\vert A_i-B_j\right\vert)\) で、答えは \(\mathrm{dp}[N][M]\) です。

時間計算量は \(\Theta(NM+N\log N+M\log M)\) であり、十分高速です。