题解
T1 购物
https://ac.nowcoder.com/acm/contest/7612/A
显然有一种暴力的方法
把依次把每个置为0，到了最后一个，值是所有的和。
那么可以往前搞，平均分配和。所以如果和不能平均分成 份就是无解。
然后可以发现每个依次操作就是最优策略。
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
#define int long long
inline int read(){
int x=0,f=0,ch=getchar();
while('0'>ch||ch>'9')f^=ch=='-',ch=getchar();
while('0'<=ch&&ch<='9')x=(x<<1)+(x<<3)+(ch^'0'),ch=getchar();
return f?-x:x;
}
const int MAX=1e5+5;
int n,T,a[MAX],ans,sum;
signed main(){
T=read();
while(T--){
n=read();sum=ans=0;
for( int i=1;i<=n;++i)a[i]=read(),sum+=a[i];
if(sum%n)puts("-1");
else{
sum/=n;
for( int i=1,x;i<=n;++i){
x=a[i]-sum;ans+=x<0?-x:x;
a[i]=sum;a[i+1]+=x;
}
printf("%lld\n",ans);
}
}
return 0;
}
查看21道真题和解析
