- 2023-10-09P9474 [yLOI2022] 长安幻世绘
题目意思:需要在元素互不相同的数列\(a\)中选出一个长度为\(m\)的元素互不相邻的子列,使得子列的极差最小。做法我们知道,对于一组数列,我们只需知道它的最大值和最小值,就可以得到它的极差。那么我们可以将数字从小到大排序,固定最小值,寻找最优的最大值,当最小值和最大值的位置固
- 2023-08-22P9474 [yLOI2022] 长安幻世绘
题目大意在元素互不相同的数列\(a\)中选出一个长度为\(m\)的元素互不相邻的子列,使得子列的极差最小。思路爆搜、\(dp\)肯定是过不了的,所以我们考虑固定某个值,赛时想到了固定最大或者最小值,然后找到另一个值,但是除了\(dp\)没想到好做法,比赛结束了才知道正解居然是同时固
- 2023-07-23题解 P9474 [yLOI2022] 长安幻世绘
看到极差,不难想到双指针。显然,如果\([l,r]\)的位置都被覆盖,那么其中最多可以选\(\lceil\frac{r-l+1}{2}\rceil\)个数。我们先将所有数离散化,排序,双指针卡取值范围。set里面存pair类型变量,表示覆盖的区间。每次将值为\(r\)的数的位置加入,在set中二分到与它相邻的区