题解：P17444 极差数组操作 / Range Minimization
jellye
·
·
题解
题意
给定序列 a，可以令任意两个元素一个减 1，一个加 3，求操作任意次后 \max_{i=1}^{n} a_i - min_{i=1}^{n} a_i 的最小值。
思路
$n = 2$ 时，令 $x = | a_1 - a_2 | \bmod 4$，则最小极差为 $\min(x, 4 - x)$。
$n \ge 3$ 时，我们分别操作 $(x,y),(y,x)$，可以让 $x,y$ 分别 $+2$。进一步地，我们可以让 $a$ 中任意 $k$ 个元素 $+ 2 \times p$，其中 $k \ge 2$，$p \ge 1$。这样，我们就可以将 $a$ 变为只由 $x$ 与 $x + 1$ 组成的序列，此时极差为 $1$。
考虑 $x \ge 3$ 时，$a$ 满足什么条件可以使 $a$ 中所有元素相等（此时极差为 $0$）。我们让 $a$ 中除 $x$ 以外的元素都 $+ 4$，然后让 $x + 3,y - 1$，这相当于让 $x,y$ 都 $- 1$。
$n$ 是奇数时，对于任意一个 $a_i = x$，我们可以让剩下 $n - 1$ 个数两两 $- 1$，这等价于令 $a_i + 1$。因此我们可以做到 $a$ 中所有元素相等，极差为 $0$。
$n$ 是偶数时，$a$ 中的奇数个数与偶数个数相等，我们对它们进行分类讨论：
- 情况一：均为偶数。此时我们可以将奇偶性相同的数两两配对，将大数不断 $- 2$ 直到等于小数，然后两者不断 $- 1$ 直到为 $0$。这样 $a$ 中所有元素相等，极差为 $0$。
- 情况二：均为奇数。这时无法两两配对，就不能将极差变为 $0$。因此极差为 $1$。
但是更改过程中，两者数量是不断变化的。考虑计算 $S = \sum_{i=1}^{n} a_i $。由于一次操作后 $S$ 加了 $2$，$S \bmod 2$ 的值是不变的。对应地，如果是情况一，$S$ 为偶数；如果是情况二，$S$ 为奇数。
## 复杂度分析
记所有测试用例的 $n$ 之和为 $N$，则时间复杂度为 $O(N)$。
## 代码
```cpp
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=200005;
int t,n,a[N];
signed main()
{
cin>>t;
while(t--)
{
cin>>n;
for(int i=1;i<=n;i++) cin>>a[i];
if(n==1) cout<<0;
else if(n==2)
{
int x=abs(a[1]-a[2])%4;
cout<<min(x,4-x);
}
else
{
int tot=0;
for(int i=1;i<=n;i++) tot+=a[i];
if(n%2==1||tot%2==0) cout<<0;
else cout<<1;
}
cout<<'\n';
}
}
```