题解：P10444 「MYOI-R3」极差
ChampionCyan
·
·
题解
官方题解说这题要用桶，但我赛时用双指针过了。
若拆分后有多个子序列且满足条件，那这个序列一定可以拆成 2 个子序列且满足条件。
操作：
拆成后的两个子序列的最大值和最小值分别是：
最小值：原来多个子序列中最小值最小的那个子序列的最小值
最大值：原来多个子序列中最小值最大的那个子序列的最小值
$b$ 子序列：
最小值：原来多个子序列中最小值最小的那个子序列的最大值
最大值：原来多个子序列中最小值最大的那个子序列的最大值
证明：
若拆分后有多个子序列且满足条件，根据题意，他们的极差一定相等。设原来的极差为 $dis$ 、原来多个子序列中最小值最小的那个子序列的最小值为 $minl$ 、原来多个子序列中最小值最大的那个子序列的最小值为 $maxl$ 。那么原来多个子序列中最小值最小的那个子序列的最大值为 $minl+dis$ 、原来多个子序列中最小值最大的那个子序列的最大值为 $maxl+dis$ 。
那么 $a$ 子序列的极差为 $maxl-minl$ ， $b$ 子序列的极差为 $(maxl+dis)-(minl+dis)=maxl-minl$ ，极差相等，符合条件。因此我们最先提出的结论正确，证毕。
根据前面的结论，我们只用知道原来的 $c$ 数组能否拆成 $2$ 个子序列能否满足条件就能得出答案。
其实刚刚的证明中我们发现，第一个子序列的最小值和第二个子区间的最大值是固定的。第一个子序列的最小值为整个序列的最小值，第二个子序列的最大值为整个序列的最大值。
关键就是如何求第一个子序列的最大值和第二个子序列的最小值。我们可以先对数组排序，再用双指针求解。
定义两个指针 $l$ 和 $r$ ，分别表示第一个子序列的最大值的位置和第二个子序列的最小值的位置。令 $l=2$ ， $r=n-1$ 。
当 $l<r$ 时，即两个子序列能够包含整个序列时，若 $maxl-c_l=c_r-minl$ ，就是当两个子序列的极差相等时， `puts("yes")` 并进入下一组数据。
否则若 $maxl-c_l<c_r-minl$ 即 $a$ 序列极差更大，那么找寻的被减数同时也是 $a$ 序列的最大值 $c_r$ 就要更小，所以我们让 $r-1$（因为排序后的 $c$ 数组是递增的，下标越小数值越小，所以调小下标）。
否则若 $maxl-c_l>c_r-minl$ 即 $b$ 序列极差更大，那么找寻的减数同时也是 $b$ 序列的最小值 $c_l$ 就要更大，所以我们让 $l+1$ （因为排序后的 $c$ 数组是递增的，下标越大数值越大，所以调大下标）。
若一直到 $l\ge r$ 时都没有解，则 `puts("No")` 。
代码:
```cpp
#include <bits/stdc++.h>
using namespace std;
int c[1000001];
int main() {
int t, id;
scanf("%d%d", &t, &id);
while (t--) {
int n;
scanf("%d", &n);
for (int i = 1; i <= n; i++)
scanf("%d", c + i);
if (id == 4) {//常数优化
if (n >= 4)
puts("Yes");
else
puts("No");
continue;
}
sort(c + 1, c + n + 1);
int l = 2, r = n - 1, minl = c[1], maxl = c[n];
while (r > l) {
int x = maxl - c[l], y = c[r] - minl;
if (x == y) {
puts("Yes");
goto out;//意思是跳到out:;行，作用直接进行下一组数据而不输出No
} else if (x > y)
l++;
else
r--;
}
puts("No");
out:;//这就是out:;行
}
return 0;
}
```