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

显然，由题意可以发现，每一次操作之后序列总和不变。

由于需要保证每一个数相同，因此我们可以做出如下判断：令 ，如果 ( 能被 整除)，那么可以达到题目要求；反之则不能达到题目要求。

下文令 表示 序列的平均数。

求最小步数时，我们发现： 只能影响 ，要使 ，只能由 操作，并且对于同一个数，+1 之后 -1 没有任何意义，所以我们从 开始，一个一个变为 ，保证 只能与 操作，到最后操作完毕时的最小步数就是答案。

代码:

#include<bits/stdc++.h>
using namespace std;

const int MAXN=1e5+10;
int n,t,a[MAXN];
typedef long long LL;
LL sum,ans;//最好开 long long

int main()
{
//    freopen(".in","r",stdin);
//    freopen(".out","w",stdout);
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d",&n);ans=0;sum=0;
        for(int i=1;i<=n;i++) scanf("%d",&a[i]);
        for(int i=1;i<=n;i++) sum+=(LL)a[i];
        if(sum%(LL)n!=0) cout<<"-1\n";
        else
        {
            int ave=sum/n;
            for(int i=1;i<=n;i++)
            {
                ans+=abs((LL)a[i]-(LL)ave);//计算答案
                a[i+1]-=ave-a[i];//改变a[i+1]，如果ave-a[i]为负数那么a[i+1]就会加上相应值
            }//这里是改变a[i],如果不理解可以手动模拟一遍
            cout<<ans<<"\n";
        }
    }
    return 0;
}