贪心w 设每个人原来的糖果数为Ai，最后的糖果数为k（即平均数） 第1个人给了第n个人X1颗糖 第i个人给了第(i-1)个人Xi颗糖（i>1） 那么ans= |X1| | X 1 | + |X2| | X 2 | +……+ |Xn| | X n | k=A1-X1+X2=A2-X2+X3=……=An-1-Xn-1+Xn=An-Xn+X1; 即X2=X1+k-A1 X3=X2+k-A2=X1+2k-A2-A1 X4=X3+k-A3=X1+3k-A3-A2-A1 …… Xn=Xn-1+k-An=X1+(n-1)k-An-1-……-A1; 设A1-k=C1,A1+A2-2k=C2,A1+A2+A3-3k=C3,……,A1+……+An-1-(n-1)k=Cn-1 则ans= |X1| | X 1 | + |X1−C1| | X 1 − C 1 | + |X1−C2| | X 1 − C 2 | +……+ |X1−Cn−1| | X 1 − C n − 1 | 转化为数轴上距离问题(X1到C1,C2,……,Cn-1的距离)，要令ans最小，只需使X1=C1,C2,……,Cn-1的中位数即可
#include<cmath> #include<cstdio> #include<cstring> #include<iostream> #include<algorithm> using namespace std; long long a[1000005],c[1000005]; inline long long read() { char ch=getchar(); while (ch<'0' || ch>'9') ch=getchar(); long long ans=0; while (ch<='9' && ch>='0') { ans=ans*10+ch-48; ch=getchar(); } return ans; } int main() { int n=read(); long long s=0; for (int i=1; i<=n; i++) { a[i]=read(); s+=a[i]; } /* if (s%n!=0) { puts("No Sulotion"); return 0; } 题目里没有说无解的情况所以注释啦，不过这样会无解的吧qwq~ */ long long k=s/n; s=0; for (int i=1; i<=n; i++) { s+=a[i]; if (i!=n) c[i]=s-k*i; else c[i]=0; } sort(c+1,c+1+n); long long x,ans=0; if (n&1) x=c[n/2+1]; else x=(c[n/2]+c[n/2+1])/2; for (int i=1; i<=n; i++) ans+=abs(x-c[i]); printf("%lld\n",ans); }