前言 搜了一圈都没有看到对“最小极差等于最大后缀平均值向上取整减去最小前缀平均值向下取整”这一结论的证明，因此在这里补一个。证明过程还是有一定的技巧性的，尤其是引理二，其中用到了一些取整函数的性质，不熟悉的同学可以自行了解。
一些记号
下标为
1 ∼ n 1\sim n 1 ∼ n 组成的连续子序列为
A 1 ∼ n A_{1\sim n} A 1 ∼ n ；
A A A 中的最小值为
min ( A ) \min(A) min ( A ) ，
A A A 中的最大值为
max ( A ) \max(A) max ( A ) ；
A A A 中前
i i i 个数组成的前缀平均值为
L ( A , i ) = S ( A 1 ∼ i ) i L(A,i)=\frac{S(A_{1\sim i})}{i} L ( A , i ) = i S ( A 1 ∼ i ) ；
A A A 的最小前缀平均值为
L ( A ) = min i = 1 n L ( A , i ) L(A)=\min_{i=1}^nL(A,i) L ( A ) = min i = 1 n L ( A , i ) ；
A A A 中第
i i i 个数开始组成的后缀平均值为
R ( A , i ) = S ( A i ∼ n ) n − i + 1 R(A,i)=\frac{S(A_{i\sim n})}{n-i+1} R ( A , i ) = n − i + 1 S ( A i ∼ n ) ；
A A A 的最大后缀平均值为
R ( A ) = max i = 1 n R ( A , i ) R(A)=\max_{i=1}^nR(A,i) R ( A ) = max i = 1 n R ( A , i ) ；
若
A i > A i + 1 A_i>A_{i+1} A i > A i + 1 ，称
( i , i + 1 ) (i,i+1) ( i , i + 1 ) 上的操作是“平衡”的。
引理一 对序列
A A A 进行任意次操作得到序列
B B B ， 则
min ( B ) ≤ ⌊ L ( A ) ⌋ \min(B)\le\lfloor L(A)\rfloor min ( B ) ≤ ⌊ L ( A )⌋ 且
max ( B ) ≥ ⌈ R ( A ) ⌉ \max(B)\ge\lceil R(A)\rceil max ( B ) ≥ ⌈ R ( A )⌉ 。
引理一证明 记序列长度为
n n n ，假设
min ( B ) > ⌊ L ( A ) ⌋ \min(B)>\lfloor L(A)\rfloor min ( B ) > ⌊ L ( A )⌋ 。令
i i i 为某个满足
L ( A , i ) = L ( A ) L(A,i)=L(A) L ( A , i ) = L ( A ) 的正整数，因为
L ( B , i ) ≥ min ( B ) L(B,i)\ge\min(B) L ( B , i ) ≥ min ( B ) ，故：
⌊ L ( B , i ) ⌋ ≥ ⌊ min ( B ) ⌋ = min ( B ) > ⌊ L ( A ) ⌋ = ⌊ L ( A , i ) ⌋ \lfloor L(B,i)\rfloor\ge\lfloor\min(B)\rfloor=\min(B)\\>\lfloor L(A)\rfloor=\lfloor L(A,i)\rfloor ⌊ L ( B , i )⌋ ≥ ⌊ min ( B )⌋ = min ( B ) > ⌊ L ( A )⌋ = ⌊ L ( A , i )⌋ 因此
L ( B , i ) > L ( A , i ) L(B,i)>L(A,i) L ( B , i ) > L ( A , i ) ，即
S ( B 1 ∼ i ) > S ( A 1 ∼ i ) S(B_{1\sim i})>S(A_{1\sim i}) S ( B 1 ∼ i ) > S ( A 1 ∼ i ) 。
然而，
∀ j ≠ i \forall j\ne i ∀ j = i ，在
( j , j + 1 ) (j,j+1) ( j , j + 1 ) 上进行的操作不会影响
S ( B 1 ∼ i ) S(B_{1\sim i}) S ( B 1 ∼ i ) ，而在
( i , i + 1 ) (i,i+1) ( i , i + 1 ) 上进行的操作使得
S ( B 1 ∼ i ) S(B_{1\sim i}) S ( B 1 ∼ i ) 变小，因此最终一定有
S ( B 1 ∼ i ) ≤ S ( A 1 ∼ i ) S(B_{1\sim i})\le S(A_{1\sim i}) S ( B 1 ∼ i ) ≤ S ( A 1 ∼ i ) ，矛盾。
对于后缀平均值的命题同理可证。
引理二 对序列
A A A 进行任意次
平衡 操作得到序列
B B B ，则
⌊ L ( A ) ⌋ = ⌊ L ( B ) ⌋ \lfloor L(A)\rfloor=\lfloor L(B)\rfloor ⌊ L ( A )⌋ = ⌊ L ( B )⌋ 且
⌈ R ( A ) ⌉ = ⌈ R ( B ) ⌉ \lceil R(A)\rceil=\lceil R(B)\rceil ⌈ R ( A )⌉ = ⌈ R ( B )⌉ 。
引理二证明 只需证明命题对单次平衡操作成立，记该平衡操作在
( i , i + 1 ) (i,i+1) ( i , i + 1 ) 上进行。不难发现，
∀ j ≠ i , L ( A , j ) = L ( B , j ) \forall j\ne i,L(A,j)=L(B,j) ∀ j = i , L ( A , j ) = L ( B , j ) ，而
L ( B , i ) = L ( A , i ) − 1 i < L ( A , i ) L(B,i)=L(A,i)-\frac{1}{i}<L(A,i) L ( B , i ) = L ( A , i ) − i 1 < L ( A , i ) ，因此
L ( B ) ≤ L ( A ) L(B)\le L(A) L ( B ) ≤ L ( A ) ，所以
⌊ L ( B ) ⌋ ≤ ⌊ L ( A ) ⌋ \lfloor L(B)\rfloor\le\lfloor L(A)\rfloor ⌊ L ( B )⌋ ≤ ⌊ L ( A )⌋ ，下面证明一定取等。
假设
⌊ L ( B ) ⌋ < ⌊ L ( A ) ⌋ \lfloor L(B)\rfloor<\lfloor L(A)\rfloor ⌊ L ( B )⌋ < ⌊ L ( A )⌋ ，则
∀ j ≠ i , ⌊ L ( B , i ) ⌋ < ⌊ L ( B , j ) ⌋ \forall j\ne i,\lfloor L(B,i)\rfloor<\lfloor L(B,j)\rfloor ∀ j = i , ⌊ L ( B , i )⌋ < ⌊ L ( B , j )⌋ 。（否则
∃ k ≠ i , ⌊ L ( B ) ⌋ = ⌊ L ( B , k ) ⌋ = ⌊ L ( A , k ) ⌋ ≥ ⌊ L ( A ) ⌋ \exists k\ne i,\lfloor L(B)\rfloor=\lfloor L(B,k)\rfloor=\lfloor L(A,k)\rfloor\ge\lfloor L(A)\rfloor ∃ k = i , ⌊ L ( B )⌋ = ⌊ L ( B , k )⌋ = ⌊ L ( A , k )⌋ ≥ ⌊ L ( A )⌋ ，矛盾）
若
i = 1 i=1 i = 1 ，则
⌊ L ( B , 1 ) ⌋ < ⌊ L ( B , 2 ) ⌋ \lfloor L(B,1)\rfloor<\lfloor L(B,2)\rfloor ⌊ L ( B , 1 )⌋ < ⌊ L ( B , 2 )⌋ ，即
A 1 − 1 < ⌊ A 1 + A 2 2 ⌋ A_1-1<\left\lfloor\frac{A_1+A_2}{2}\right\rfloor A 1 − 1 < ⌊ 2 A 1 + A 2 ⌋ 。讨论
A 2 A_2 A 2 的大小：若
A 2 ≤ A 1 − 2 A_2\le A_1-2 A 2 ≤ A 1 − 2 ，则
⌊ A 1 + A 2 2 ⌋ ≤ A 1 − 1 \left\lfloor\frac{A_1+A_2}{2}\right\rfloor\le A_1-1 ⌊ 2 A 1 + A 2 ⌋ ≤ A 1 − 1 ，矛盾；若
A 2 = A 1 − 1 A_2=A_1-1 A 2 = A 1 − 1 ，则
⌊ A 1 + A 2 2 ⌋ = A 1 − 1 \left\lfloor\frac{A_1+A_2}{2}\right\rfloor= A_1-1 ⌊ 2 A 1 + A 2 ⌋ = A 1 − 1 ，亦矛盾。
若
i > 1 i>1 i > 1 ，一方面有
⌊ L ( B , i ) ⌋ < ⌊ L ( B , i − 1 ) ⌋ \lfloor L(B,i)\rfloor<\lfloor L(B,i-1)\rfloor ⌊ L ( B , i )⌋ < ⌊ L ( B , i − 1 )⌋ ，因此
L ( B , i ) < L ( B , i − 1 ) L(B,i)<L(B,i-1) L ( B , i ) < L ( B , i − 1 ) ，展开并整理得到：
S ( A 1 ∼ i − 1 ) > ( i − 1 ) ( A i − 1 ) S(A_{1\sim i-1})>(i-1)(A_i-1) S ( A 1 ∼ i − 1 ) > ( i − 1 ) ( A i − 1 ) 另一方面，对
L ( B , i ) L(B,i) L ( B , i ) 与
L ( B , i + 1 ) L(B,i+1) L ( B , i + 1 ) 作差，利用
A i + 1 ≤ A i − 1 A_{i+1}\le A_i-1 A i + 1 ≤ A i − 1 以及前面的不等式整理得到：
L ( B , i ) − L ( B , i + 1 ) > − 1 i + 1 L(B,i)-L(B,i+1)>-\frac{1}{i+1} L ( B , i ) − L ( B , i + 1 ) > − i + 1 1 将不等式左边拆成“整数部分加小数部分”的形式，整理得到：
{ L ( B , i ) } > ⌊ L ( B , i + 1 ) ⌋ − ⌊ L ( B , i ) ⌋ − 1 i + 1 + { L ( B , i + 1 ) } \{L(B,i)\}>\lfloor L(B,i+1)\rfloor-\lfloor L(B,i)\rfloor-\frac{1}{i+1}+\{L(B,i+1)\} { L ( B , i )} > ⌊ L ( B , i + 1 )⌋ − ⌊ L ( B , i )⌋ − i + 1 1 + { L ( B , i + 1 )} 其中
⌊ L ( B , i + 1 ) ⌋ − ⌊ L ( B , i ) ⌋ ≥ 1 , { L ( B , i + 1 ) } ≥ 0 \lfloor L(B,i+1)\rfloor-\lfloor L(B,i)\rfloor\ge 1,\{L(B,i+1)\}\ge 0 ⌊ L ( B , i + 1 )⌋ − ⌊ L ( B , i )⌋ ≥ 1 , { L ( B , i + 1 )} ≥ 0 ，因此
{ L ( B , i ) } > i i + 1 \{L(B,i)\}>\frac{i}{i+1} { L ( B , i )} > i + 1 i 。但
L ( B , i ) L(B,i) L ( B , i ) 可表示为分母为
i i i 的有理数，因此
{ L ( B , i ) } ≤ i − 1 i \{L(B,i)\}\le\frac{i-1}{i} { L ( B , i )} ≤ i i − 1 ，矛盾。
综上，一定有
⌊ L ( A ) ⌋ = ⌊ L ( B ) ⌋ \lfloor L(A)\rfloor=\lfloor L(B)\rfloor ⌊ L ( A )⌋ = ⌊ L ( B )⌋ ，同理可证明
⌈ R ( A ) ⌉ = ⌈ R ( B ) ⌉ \lceil R(A)\rceil=\lceil R(B)\rceil ⌈ R ( A )⌉ = ⌈ R ( B )⌉ 。
最优解的构造及证明 对于长度为
n n n 的序列
A A A ，在其上反复使用平衡操作，直到得到单调不减的序列
B B B 。由于
B B B 单调不减，显然有
min ( B ) = B 1 = L ( B ) = ⌊ L ( B ) ⌋ \min(B)=B_1=L(B)=\lfloor L(B)\rfloor min ( B ) = B 1 = L ( B ) = ⌊ L ( B )⌋ 以及
max ( B ) = B n = R ( B ) = ⌈ R ( B ) ⌉ \max(B)=B_n=R(B)=\lceil R(B)\rceil max ( B ) = B n = R ( B ) = ⌈ R ( B )⌉ 。根据引理二，
⌊ L ( B ) ⌋ = ⌊ L ( A ) ⌋ \lfloor L(B)\rfloor=\lfloor L(A)\rfloor ⌊ L ( B )⌋ = ⌊ L ( A )⌋ 且
⌈ R ( B ) ⌉ = ⌈ R ( A ) ⌉ \lceil R(B)\rceil=\lceil R(A)\rceil ⌈ R ( B )⌉ = ⌈ R ( A )⌉ ，因此序列
B B B 的极差
max ( B ) − min ( B ) = ⌈ R ( A ) ⌉ − ⌊ L ( A ) ⌋ \max(B)-\min(B)=\lceil R(A)\rceil-\lfloor L(A)\rfloor max ( B ) − min ( B ) = ⌈ R ( A )⌉ − ⌊ L ( A )⌋ 。
另一方面，根据引理一，无论在
A A A 上进行怎样的操作，最终得到的序列
C C C 一定满足
max ( C ) − min ( C ) ≥ ⌈ R ( A ) ⌉ − ⌊ L ( A ) ⌋ \max(C)-\min(C)\ge\lceil R(A)\rceil-\lfloor L(A)\rfloor max ( C ) − min ( C ) ≥ ⌈ R ( A )⌉ − ⌊ L ( A )⌋ ，因此上述序列
B B B 已经达到了最优解，故最终答案为
⌈ R ( A ) ⌉ − ⌊ L ( A ) ⌋ \lceil R(A)\rceil-\lfloor L(A)\rfloor ⌈ R ( A )⌉ − ⌊ L ( A )⌋ 。
代码 CPP #include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
using ll = long long ;
int main () int t;
cin >> t;
while (t--) {
int n;
cin >> n;
vector<ll> a (n) ;
for (auto & x : a)
cin >> x;
vector<ll> pre_avg (n) , suf_avg (n) ;
pre_avg[0 ] = a[0 ];
for (int i = 1 ; i < n; i++)
pre_avg[i] = pre_avg[i - 1 ] + a[i];
for (int i = 0 ; i < n; i++)
pre_avg[i] /= i + 1 ;
suf_avg[n - 1 ] = a[n - 1 ];
for (int i = n - 2 ; i >= 0 ; i--)
suf_avg[i] = suf_avg[i + 1 ] + a[i];
for (int i = n - 1 ; i >= 0 ; i--)
suf_avg[i] = (suf_avg[i] + n - i - 1 ) / (n - i);
cout << *ranges::max_element (suf_avg) - *ranges::min_element (pre_avg) << '\n' ;
}
}