专题探究：极差

· · 个人记录

专题探究：极差

极差的性质，这种东西没有必要讲，毕竟只要善于分析就 ok 了；我们要讨论的主要是解题思路。

极差，最大的特点在于两端不确定性，即最大值与最小值需要同时确定。

由此，我们推想出一种思路：一端枚举，一端加速（如二分等技巧）。当然，还有一种非常重要的思想：双指针，这也就是锻炼思维能力的关键。

来看例题，只有实践才最有意义

小题狂做

小 z 遇到了几道有关极差的算法设计题，请你帮他完成：

  1. 给定一个长为 n 的数组，现在要把它分为 k 段，使得每一段里极差的最大值尽可能小，问最小值为多少。

  2. 给出一个长度为 n 的严格单调增的序列，将其分成 k 段，使得每一段的极差的和最小，求这个最小的和。（每段长度至少为1，当长度为1时，其极差为0）

  3. 给定一个长为 n 的数组 a，你可以进行至多 m 次操作，每次操作可以选定数组里的一个下标，若为数组中的最大值则变为数组中的最小值；若为数组中的最小值则变为数组中的最大值；否则不能操作。问经过操作后，数组极差最小是多少。

解法：

  1. 选择的数越多，极差必然会越大。最大值最小问题，满足二分性质，直接做即可。

  2. 简单思维题：如果不分段，极差为 a_n-a_1 ；分开一次，极差和为 a_n-a_i+a_{i-1}-a_1，也就是最初的极差减去了中间相邻两项差。直接做即可。

  3. 先把元素排好序，然后双指针：确定好最小值与最大值后，可以知道最小需要花费的操作次数：设小于最终最小值的数有 x 个，大于最终最大值的数有 y 个，那么最少操作次数为 x+y+\min(x,y) 次。

最小区间

给定一个长为 n 的数组 a，求出其中的一个区间，使得 “极差减去区间长度” 最大（max-min-len）。

即：你有一个长度为 n 的序列 a，它的一个区间 [l,r] 的价值是

首先能发现一个性质：区间两端分别为最大值与最小值，证明很简单。

本题方法有很多，这里简单介绍两种：

1.点对问题套路：枚举右端点 r，假定右端点的数字为最大值，那就要求出每个位置 min+len 即 a_i+r-i+1 的值，可化简只维护 a_i-i，求一个小于 r 的 i 使得 a_i-i 值最小，变量维护即可；右端点为最小值时同理可求。

联想：[NOIP2016]《天天爱跑步》这道题，也是利用同类变量归类，再分两类讨论的方法解决的，这是非常基本的做题技巧。

2.不用开数组，且代码极为简短的神级做法：

cin >> x;
mn = min(mn + 1, x), mx = max(mx - 1, x);
ans = max(ans, mx - mn - 1);

互不相邻

给定一个长为 n 的数组 a，元素互不相同。选出其中互不相邻的 m 个数，使选出的数极差最小。

本题之前我有讲过，一开始我并不知道如何去解决。

先是考虑到枚举最小值，最大值的确定满足二分性质，贪心选择数，判断能选的数超过 m 则返回 true，再看看能不能双指针优化，可惜这样只能拿部分分。

小思考：“排序”这一想法没问题：极差和元素大小有关。“元素互不相同”一定是解题重要的一步，“互不相邻”限制比较大。

我们不二分，直接“双指针”试试看：每次右端点增加时，判断最多选出几个数，如果成功就让左端点增加。

第一个办法，维护区间（由于区间不重叠，满足单调性且不会重复），新来一个点，我们看它是否与左右区间相邻，相邻合并，不相邻开拓。离开一个点，也是如此，相邻分裂，不相邻消失。更新可选的数，可以使用set，每次更新（-原来的值+现在的值）进行类似反悔操作的维护（[APIO/CTSC2007] 数据备份 把“极差最小”改为了“和最小”，也运用了类似做法）

第二个办法，线段树，我们知道每个极长区间（即不能扩展得更大的区间）长度为 len，则能选择 \lfloor len/2 \rfloor +1 个数。线段树区间合并可以很容易维护连续段，我们依旧采用双指针，只是维护方式使用线段树而已。

卡牌游戏

Alice 有 n 张卡牌，第 i（1 \le i \le n）张卡牌的正面有数字 a_i，背面有数字 b_i，初始时所有卡牌正面朝上。

现在 Alice 可以将不超过 m 张卡牌翻面，即由正面朝上改为背面朝上。Alice 的目标是让最终朝上的 n 个数字的极差（最大值与最小值的差）尽量小。请你帮 Alice 算一算极差的最小值是多少。

数据保证卡牌上的 2 n 个数字互不相同，且卡牌按照 a_i 升序给出。

本题也是有很多做法的，我们拓宽一下视野，都来看一看。

第一种做法：二分法

二分极差的值为 ans，先确定左端点的值 l，于是能确定右端点为 r，由于 a 数组已排序，就可以确定 a 数组中前后缀有多少张要翻面的牌，并判断 b 数组前后缀最小值是否大于 l 且最大值小于 r。可以用数组存储前后缀RMQ，复杂度 O(nlogn)。

第二种做法：全部排序+双指针

收集所有类别（即获得了 n 张不同的牌），最经典的双指针问题，但是再要加上选择的 a 牌不低于 n-m 张的限制。每次扫描成功将左端点向右移动，最后得出答案。虽然双指针复杂度 O(n)，但是全体排序复杂度又会上升至 O(nlogn)。

第三种做法：单调性

你或许已经意识到了这件事：结合第一种做法以及 a 升序，发现所要翻转的卡牌一定是数组的前后缀。并且，本题不存在反悔，m=1 时选的牌在 m>1 时也一定会选。

先从最小的数开始翻转，如果它会变得更小，那一定是不优的，排除；如果它比最大值来得小，那一定是可以选择的；如果比最大值更大，那就需要同时翻转最大值。再以同样的方式翻转最大的数。

这就相当于三种策略中选择一种：翻转最小、翻转最大、同时翻转。这下复杂度就是 O(n+m) 了。

Warning! 魔王来临

[春季测试 2023] 密码锁

题目描述

寒假过后，小 I 回到学校，发现自己忘记了自行车锁的密码，于是请你帮忙。

小 I 自行车上的密码锁有 n 个拨圈，每个拨圈有 k（k \leq 4）格。密码锁上的每一格都包含一个正整数，其中第 j 个拨圈的第 i 格上的正整数为 a _ {i, j}。

（一个锁的例子，其中 k = n = 3，每列表示一个拨圈，拨圈的格子从上往下编号。）

你可以对每个拨圈拨若干次（也可以不拨），每拨一次拨圈，它的格子就会进行一次轮换。形式化地，拨第 j 个拨圈一次，则会让第 j 个拨圈上第 i 格的数字移动到第 ((i \bmod k) + 1) 格，其他拨圈不动。

（一个拨动拨圈的例子，对左侧的锁拨一次第二个拨圈得到右侧的锁。）

为了方便记忆，小 I 设定密码时要求同一行上的数字尽可能靠近。 形式化地，对于 1 \leq i \leq k，定义密码锁第 i 行的松散度为

c(i) = \max \limits _ {j = 1} ^ n a _ {i, j} - \min \limits _ {j = 1} ^ n a _ {i, j}

同时定义整个密码锁的松散度为

C = \max \limits _ {1 \leq i \leq k} c(i)

因为能开锁的状态满足 C 尽可能小，因此小 I 希望你找出最小的 C 值。

输入格式

本题有多组测试数据，题目保证一个测试点中所有测试数据的 k 相同。

第一行包含两个正整数 T, k，分别表示测试数据组数和密码锁拨圈上的格数。

接下来一共 T 组数据，每组数据格式如下：

第一行包含一个正整数 n，表示拨圈数。

接下来 k 行，每行包含 n 个正整数，其中第 i 行第 j 个整数 a _ {i,j} 表示密码锁第 j 个拨圈上第 i 格对应的数字。

注意输入的矩阵中每一列对应一个拨圈，而非每一行对应一个拨圈。

输出格式

对于每组数据，输出一行包含一个整数，表示所有方案中 C 的最小值。

样例输入

2 3
3
1 2 1
2 3 2
3 1 3
2
1 2
2 1
1 2

样例输出

0
1

提示

【样例解释】

第一组样例对应题目描述中的例子。 在拨第二个拨圈一次后，每个拨圈都是 \{1, 2, 3\}，此时松散度为 0。 容易证明无论如何松散度都不可能小于 0，因此输出 0。

【数据范围】

设 \sum n 为一个测试点中所有测试数据的 n 的和。

对于所有数据，保证 1 \leq T，1 \leq k \leq 4，1 \leq a _ {i ,j} \leq 3 \times 10 ^ 4。

第一类测试点共有十二个，保证 k \leq 3，n \leq 5 \times 10 ^ 4，\sum n \leq 1.5 \times 10 ^ 5。

第二类测试点共有八个，保证 k = 4，n \leq 10 ^ 4，\sum n \leq 3 \times 10 ^ 4。

本题难度较大，就当作一道思考题吧~如果有很好的思路可以分享给我哦！