最优解中一定是分成连续的 $k$ 段。

先考虑 $n$ 大的情况，这时候每一段的最小值一定取到中位数，可以预处理后 $O(1)$ 计算一个区间的代价。二分答案之后，双指针求出每个点开始的最长的区间，如果从 $i$ 开始 $k$ 个区间可以覆盖到 $i+n$ 说明有解。因为数据随机，可以假设 $0$ 到 $2n/k$ 中一定有一个端点，每个段点跳 $k$ 步，所以可以在 $O(n)$ 时间里完成一轮二分。总时间复杂度 $O(n\log nL)$。

$n$ 小的时候可以暴力预处理每个区间的代价。