答案显然具有可二分性，于是我们套上二分，现在问题转化为是否有一个长度为 $s$ 的区间，满足对于这个区间的 $\sum \left| d_{i} \right| \leq K$。

现在我们考虑设一个函数 $f(x)$，表示 $[x,x+s-1]$ 这个区间的 $\sum \left| d_{i} \right|$。现在我们思考每一个区间 $[L_{i},R_{i}]$ 对 $f(x)$ 的贡献 $g(x)$，可以发现这是一个分段函数的形式，式子如下。

$$g(x)= \left\{ \begin{align} & -x+L_{i} \, & x \leq L_{i} \nonumber \\ & 0 \, & L_{i} < x < R_{i}-s+1 \nonumber \\ & x-(R_{i}-s+1) & x \geq R_{i}-s+1 \nonumber \end{align} \right.$$

这是一个凸函数，所以最小值必定取在折点处。更进一步，还有 $g(x)$ 分段函数的两部分是独立的，那么我们可以分别对 $L,R$ 排序，然后扫一遍求出所有的 $f(x)$ 即可，单次 $\mathcal{O}(n)$，那么总复杂度就是 $\mathcal{O}(n \log n)$。