本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-03-13 14:30:15

赛时没开 long long 吃了 5 个罚时在这题。

做法

先计算出 $a_{i+1}-a_i$ 的最大值，如果这个最大值多次出现，那么显然答案无法改变，直接把最大值输出就行。

然后，考虑如何搭配 $f,d$ 使得插入后的值能更好的减少最大值。

显然，设最优方案为 $f_i+d_j$，另设 $a_{p+1}-a_p$ 是 $a$ 相邻元素差值的最大值。那么 $f_i+d_j$ 应尽可能均分 $a_{p+1}-a_p$，也就是说 $f_i+d_j$ 应尽可能接近 $\frac{a_{p+1}-a_p}{2}$。

此时解决方案已经很明显了。

枚举 $f_i$，并二分 $d_j$，找出使得 $f_i+d_j$ 能达到的最大的小于 $\frac{a_{p+1}-a_p}{2}$ 的值对应的 $d_j$，以及使得 $f_i+d_j$ 能达到的最小的大于 $\frac{a_{p+1}-a_p}{2}$ 的值对应的 $d_j$。以上操作用 lower_bound 就可以解决。

注意计算 $\frac{a_{i}+a_{i+1}}{2}$ 如果先加后除，那么会爆 int，我赛时因此吃了 5 个罚时。