算法 中位数,贪心
首先,最终每个人的金币数量可以计算出来,它等于金币总数除以人数n,接下来我们用M表示每人最终拥有的金币数。假设在这个过程中,可以设x2表示2号给了1号多少个金币,x3,x4类似。由于是环型,x1指的是1号给了4号多少金币。
对于编号为i的人,初始为Ai,则1号,他最终剩余A1-x1+x2=M。
时间复杂度
参考文献
C++ 代码
#include<iostream>
#include<algorithm>
#include<math.h>
using namespace std;
const int N = 1000010;
typedef long long ll;
int n;
ll init[N],c[N];
int main(){
while(cin>>n){
ll sum=0;
for(int i=0;i<n;i++){
cin>>init[i];
sum+=init[i];
}
ll avg=sum/n;
c[0]=0;
for(int i=1;i<n;i++){
c[i] =c[i-1] + init[i]-avg;
}
sort(c,c+n);
ll res = c[n/2],ans=0;
for(int i=0;i<n;i++){
ans = ans+abs(res-c[i]);
}
cout<<ans<<endl;
}
return 0;
}