经典算法题
均分纸牌
[传送门](P1031 [NOIP 2002 提高组] 均分纸牌 - 洛谷)
题意：
现有$n$堆纸牌，需要让每堆纸牌牌数相等。相邻的纸牌堆可以交换任意个纸牌，求最小交换次数
样例
4
9 8 17 6
3
平均数为$10$ 显然可以有$17$往左移动两次，往右移动一次得到答案
思路：
贪心 不妨先用每堆牌数减去平均数，这样每一堆转换为多/少出来的牌数 可以从左往右遍历整个数组，如果当前需要的牌数不为$0$，说明需要移动。并把所有需要的牌数转移到下一堆上。
代码：
n=int(input())
a=list(map(int,input().split()))
ans=0
sum=0
for x in a:
sum+=x
ave=sum//n
for i in range(0,n):
a[i]-=ave
for i in range(0,n):
if a[i]:
a[i+1]+=a[i]
ans+=1
a[i]=0
print(ans)
环形问题
[传送门](P2512 [HAOI2008] 糖果传递 - 洛谷) 是纸牌问题的另一种形式
此时$n$堆牌围成一个圈，可以向左/右传递牌
思路：
如果原数组为$A$，平均数为$ave$ 设$X_i$为每一堆牌往左传递的个数，往右传递记为负数
对于$i (1\leq i \lt n)$ , 有$A_i-X_i+X_{i+1}=ave$ 有$A_n - X_n + X_1=ave$
即$X_i = X_{i-1}+ ave - A_{i-1}$ $X_2 = X_1+ave-A_1$ $X_3 = X_2+ave-A_2 = X_1+2ave-A_1-A_2$ $X_n =X_1+(n-1) ave - A_1 - A_2 …-A_{n-1}$ $X_1 = X_n+ ave -A_n = X_1 + nave - A_1…A_n$
令$C_i = -i ave + A_1 .. +A_i$ 则$X_i = X_1-C_{i-1}$ , $X_1 = X_1-C_n$
目标要求$X_i$的绝对值之和最小
即$|X1-C_{i-1}|$的和最小
因此问题转换为货舱选址问题 预处理出$C$数组，令$X_1$为其中位数即可
n=int(input())
a=list(map(int,input().split()))
sum=0
for x in a:
sum+=x
k=sum//n
ans=0
c=[0]*(n+1)
lst=0
for i in range(1,n+1):
lst+=a[i-1]
c[i]=-i*k+lst
c[1:n+1]=sorted(c[1:n+1])
x1 = c[(n+1)//2]
for i in range(1,n+1):
ans+=abs(x1-c[i])
print(ans)