P3641 [APIO2016] 最大差分 题解

选自 11 月做题笔记。

031. P3641 [APIO2016] 最大差分

第一问是简单的，直接从两端往中间问即可。

对于第二问，先求出序列的最小值 $mi$ 和最大值 $mx$，此时根据抽屉原理可知答案有下界 $\frac{mx-mi}{n-1}$。

这个时候考虑给 $[mi,mx]$ 这个区间每 $\frac{mx-mi}{n-1}$ 个元素分块，根据抽屉原理可知最后 gap 最大的位置 $a_{i+1}-a_i$ 一定不会让 $a_i$ 和 $a_{i+1}$ 出现在同一个块内。因此直接对每个块询问一次最小值和最大值，然后若该段区间内有元素，就把答案和上一次询问出的最大值做个差并更新答案即可。最后记得处理 $mx$ 和最后一次问出的最大值的差。

然后考虑证明正确性：

• 询问 $mi,mx$ 直接对区间 $[0,10^{18}]$ 问即可，花费为 $n+1$。
• 然后对每一个块都询问一次，总共会问 $n-1$ 次，总共出现 $n-2$ 个点，因此该部分总花费为 $(n-1)+(n-2)=2n-3$。

总花费为 $(n+1)+(2n-3)=3n-2\le 3n$，符合题目要求，可以通过该题。