P3156 [CQOI2011] 分金币

算是一道数学题。 设$p[i]$为第$i$个人分给第$i-1$个人的数量（第一个人分给最后一个人） 且$p[i]$可正可负，负数表示第$i-1$个人给第$i$个人的 则题目所求为$Ans=|p[1]|+|p[2]|+……|p[n]|$的最小值 设平均数为$ave$ 则$ave=a[i]+p[i+1]-p[i]$ 设$w[i]=p[i+1]-p[i]=ave-a[i]$ $s[i]=w[1]+w[2]+……+w[i]$（即w的前缀和） 则$p[i]=p[1]+s[i-1]$ 所以$Ans=|p[1]|+|p[1]+s[1]|+……|p[1]+s[n-1]|$ 设$Q=-p[1]$ 则$Ans$的含义就是$0,s[1],s[2]……s[n]$到$Q$的距离之和的最小值 所以这个$Q$就是$s$数组中的中位数了 ``` #include<cstdio> #include<cstring> #include<cctype> #include<cstdlib> #include<algorithm> #define reg register using namespace std; typedef long long ll; const int N=1e5+5; int n,a[N],tot; ll sum[N],ans,q; inline int read() { int x=0,w=1; char c=getchar(); while (!isdigit(c)&&c!='-') c=getchar(); if (c=='-') c=getchar(),w=-1; while (isdigit(c)) { x=(x<<1)+(x<<3)+c-'0'; c=getchar(); } return x*w; } int main() { n=read(); for (reg int i=1;i<=n;i++) a[i]=read(),tot+=a[i]; tot/=n; for (reg int i=1;i<=n;i++) a[i]-=tot,sum[i]=sum[i-1]+a[i]; sort(sum+1,sum+n+1); ll q=(n&1)?sum[(n>>1)+1]:(sum[n>>1]+sum[(n>>1)+1])>>1; for (reg int i=1;i<=n;i++) ans+=abs(sum[i]-q); printf("%lld\n",ans); return 0; } ```