环形均分纸牌问题。用A[i]表示糖果数，sum表示目标的糖果数量。用X[i]表示从i + 1移动到i的糖果的个数（可+可-）。由此可以得到式子A[i] + X[i] - X[i - 1] = sum。我们可以得到这样的n - 1个方程（第n个可以由前n - 1个推导）。但是这样不足以求解。我们进行以下变形：

A[2] + X[2] - X[1] = sum => X[2] = X[1] + sum - A[2]

A[3] + X[3] - X[2] = sum => X[3] = X[2] + sum - A[3] = X[1] + (sum - A[2]) + (sum - A[3])

设W[1] = 0, W[2] = A[2] - sum, W[i] = W[i - 1] + A[i] - sum,则 X[i] = X[1] - W[i]

所以Ans = sigma (|X[1] - W[i]|), 1 <= i <= n

而这个式子的几何意义是找一个点，使得这个点到W[i]所对应的每一个点的距离的和最小。所以X[1]应该取W[i]的中位数。

 

#include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            
             using namespace std; typedef long long LL; #define MAXN 1000010 int a[MAXN],c[MAXN];int n;LL sum,ans; int main(){ scanf("%d",&n); for (int i=1;i<=n;i++) { scanf("%d",&a[i]); sum+=a[i]; } sum/=n; for (int i=2;i<=n;i++) c[i]=c[i-1]+a[i]-sum; sort(c+1,c+n+1); int m=c[n>>1|1]; for (int i=1;i<=n;i++) ans+=abs(c[i]-m); printf("%lld",ans); return 0;}