题目描述

难度分:$1900$

输入$T(\leq 10^5)$表示$T$组数据。所有数据的$n$之和$\leq 2 \times 10^5$。

每组数据输入$n(1 \leq n \leq 2 \times 10^5)$和长为$n$的数组$a(1 \leq a[i] \leq 10^{12})$。

有$n$堆石子，每堆石子的个数是$a[i]$。你可以执行任意次如下操作：

• 把$a[i]$的一颗石子移动到$a[i+1]$中。

输出$max(a)-min(a)$的最小值。

输入样例

5
1
1
3
1 2 3
4
4 1 2 3
4
4 2 3 1
5
5 14 4 10 2

输出样例

0
2
1
1
3

算法

贪心+前后缀和

题目所给的操作就是可以让前面的数变小，后面的数变大。而我们的目的就是要让答案尽量接近均值，最小值我们可以从前往后计算前缀平均值（向下取整），最大值我们可以从后往前计算后缀平均值（向上取整）得到。

答案就是后缀平均值的最大值减去前缀平均值的最小值。

复杂度分析

时间复杂度

遍历两次数组计算前后缀和就能求得答案，因此时间复杂度为$O(n)$。

空间复杂度

除了输入的数组$a$，仅使用了有限几个变量，额外空间复杂度为$O(1)$。

C++ 代码

#include <bits/stdc++.h>

using namespace std;
typedef long long LL;

const int N = 200010;
int T, n;
LL a[N];

int main() {
    scanf("%d", &T);
    while(T--) {
        scanf("%d", &n);
        for(int i = 1; i <= n; i++) {
            scanf("%lld", &a[i]);
        }
        LL sum1 = 0, sum2 = 0, ans1 = 1e18, ans2 = -1e18;
        for(int i = 1; i <= n; i++) {
            sum1 += a[i];
            ans1 = min(ans1, sum1 / i);
        }
        for(int i = n; i >= 1; i--) {
            sum2 += a[i];
            ans2 = max(ans2, (sum2 + n - i) / (n - i + 1));
        }
        printf("%lld\n", ans2 - ans1);
    }
    return 0;
}