CF1941F 题解

__vector__ · 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 个罚时。