2020牛客NOIP赛前集训营-普及组（第五场） C

C T3 最少移动

题面

https://ac.nowcoder.com/acm/contest/7612/C

思路

原题，首先考虑能不能均分，如果能均分显然 能被 整除。

如果能整除，那么考虑下面这样的序列

显然是两个 需要分给 怎么分呢？

仔细观察上面这个过程，其实“分”的过程等于向右边“借”的过程，我们只要知道平均数，然后直接问右边要，右边的数自然会向他的右边要，就算出现了负数也没问题。

于是，代码就非常显然了。记得开 long long

代码

#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <cstring>
#include <string>
#include <queue>
#include <stack>
#include <vector>
#include <set>
#include <map>

using std::cin;using std::cout;using std::cerr;using std::endl;

#define rep(i,a,b) for(int i = a;i <= b;++i)
#define per(i,a,b) for(int i = a;i >= b;--i)

const int mmax = 1e5;
long long l,r,ans,sum;
long long T,n,a[mmax + 10];
int main(){

    std::ios::sync_with_stdio(0);
    cin.tie(0);

    cin>>T;

    while(T--){
        cin>>n;

        l = 1,r = n,ans = 0,sum = 0;

        rep(i,1,n){
            cin>>a[i];
            sum += a[i];
        }

        if(sum % n){
            cout<<-1<<endl;
            continue;
        }

        sum /= n;

        rep(i,1,n){
            ans += std::abs(sum - a[i]);
            a[i + 1] += a[i] - sum;            
        }

        cout<<ans<<endl;

    }



    return 0;
}