题解

思路

只考虑最终要落入区间的那些数。

做法

若把 $A_3,\ldots,A_N$ 排序，选定的 $M$ 个数一定可以替换为排序后某个连续的长度为 $M$ 的窗口而不增大代价：窗口内部的数本来就位于最小值和最大值之间，决定代价的只有两端。对于窗口 $[l,r]$，把左端纳入下界所需的代价是 $\max(0,A_1-A_l)$，把右端纳入上界所需的代价是 $\max(0,A_r-A_2)$，二者之和就是这个窗口的最小代价。

枚举所有满足 $r=l+M-1$ 的窗口并取上述代价的最小值即可。

复杂度

排序需要 $O(N\log N)$ 时间，窗口扫描为 $O(N)$，额外空间为 $O(N)$。