P10059 Choose 题解

link 本题为原T1

给定长度为 $n$ 的序列 $a$。给你一个不超过 $n$ 的正整数 $k$，你需要选出 $k$ 个位置不同的长度相同的区间，记为 $[l_1,r_1],[l_2,r_2],[l_3,r_3],\dots,[l_k,r_k]$。你获得的分数为所有区间极差的最小值。你希望最大化自己的分数，并求出此前提下区间长度的最小值。

---

简单题。

不考虑区间长度。显然固定一个区间的左端点，右端点不断往右，极差是单调不下降的。

那么最大的分数就是 $k$ 个长度为 $n-k+1$ 的区间叠放的最小值。使用 RMQ 维护极差。

那么得到这个最小值以后，考虑二分区间长度。

此时可能的区间个数是要 $>k$ 的，但是这些区间有一些的极差比 ans 要小，这些区间不能要。

统计一下能要的区间个数是否 $\geq k$ 即可。

复杂度 $O(n\log n)$ 。由于区间叠放，因此可以使用滑动窗口把 log 丢掉。