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; }