..
AcWing 109. 天才ACM
首先，对于一个集合 $S$，显然应该取 $S$ 中最大的 $M$ 个数和最小的 $M$ 个数，最大和最小构成一对、次大和次小构成一对 $\cdots$ 这样求出的 “校验值” 最大。
而为了让数列 $A$ 分成的段数最少，每一段都应该在 “校验值” 不超 $T$ 的前提下，尽量包含更多的数。
所以我们从头开始对 $A$ 进行分段，让每一段尽量长，到达结尾时分成的段数就是答案。
于是，需要解决的问题为：当确定一个左端点 $L$ 之后，右端点 $R$ 在满足 $A[L] \sim A[R]$ 的 “校验值” 不超过 $T$ 的前提下，最大能取到多少。
求长度为 $N$ 的一段的 “校验值” 需要排序配对，时间复杂度为 $\mathcal{O}(N \log{N})$。
当 “校验值” 上限 $T$ 比较小时，最终右端点 $R$ 却可能只扩展了一点儿，浪费了很多时间。
我们需要一个与右端点 $R$ 扩展的长度相适应的算法——倍增。
- 初始化 $p = 1$，$R = L$；
- 求出 $[L, R + p]$ 这一段区间的 “校验值”，若 “校验值” $\leq T$，则 $R$ $+=$ $p$，$p$ $*=$ $2$，否则 $p$ $/=$ $2$；
- 重复上一步，直到 $p$ 的值变为 $0$，此时 $R$ 即为所求。
上面这个过程至多循环 $\mathcal{O}(\log{N})$ 次，每次循环对长为 $\mathcal{O}(R - L)$ 的一段进行排序，完成整个题目的求解累计扩展长度为 $N$，所以总体时间复杂度为 $\mathcal{O}(N \log^2{N})$。
实际上我们每次求 “校验值” 时可以不用快速排序，而是采用类似归并排序的方法，只对新增的长度部分排序，然后合并新旧两段，这样总体时间复杂度可以降低到 $\mathcal{O}(N \log{N})$。
完整代码：天才ACM.cpp