计蒜客 聪明的班主任（思维）

题目链接：https://nanti.jisuanke.com/t/15723

题解：一道挺好的思维题，有点难想。在这里举几个例子如果都过了的话应该就是对了。

0 6 0 6->3-------0 6 6->4--------3 4 6 3 4 10->5---------1 2 6 1 2 5 4->3--------4 0 1 3->2

大致思路就是先将所有数都减去它们的平均值然后再求前缀和。答案就是max（abs（负的最大值），正的最大值）

为什么是这样呢。其实前缀表示的是这些数变成0所要经过的数，所以只要取最大的那个就行了。

#include <iostream>
#include <cstring>
#include <cstdio>
using namespace std;
const int M = 1e4 + 10;
typedef long long ll;
ll a[M] , pre[M];
int main() {
    int t;
    scanf("%d" , &t);
    while(t--) {
        ll n;
        scanf("%lld" , &n);
        ll sum = 0;
        for(int i = 1 ; i <= n ; i++) {
            scanf("%lld" , &a[i]);
            sum += a[i];
        }
        if(sum % n == 0) {
            ll gg = sum / n;
            for(int i = 1 ; i <= n ; i++) {
                a[i] -= gg;
            }
            pre[0] = 0;
            for(int i = 1 ; i <= n ; i++) {
                pre[i] = pre[i - 1] + a[i];
            }
            ll MIN = 0 , MAX = 0;
            for(int i = 1 ; i <= n ; i++) {
                MIN = min(MIN , pre[i]);
                MAX = max(MAX , pre[i]);
            }
            printf("%lld
" , max(-MIN , MAX));
        }
        else printf("-1
");
    }
    return 0;
}