纸牌均分问题_牛客博客

首先，如果有某序列 $a_{i}$ ，则 $\sum_{i = 1}^{n} ∣ a_{i} - k ∣$ 取最小值时，k为 $a_{i}$ 的中位数。（因为如果是pos，则pos向靠近中位数的位置移动能更小），这个性质也能dp

有n个人站成一排，每个人有 $a_{i}$ 张纸牌，求最小移动次数使得每个人纸牌数一样，一张纸牌交给旁边的人记为一次移动。
如果tot是n的倍数，则有解，设t=tot/n
遍历一遍，对于第i个人，ans+=abs(a[i]-t)，a[i+1]-=t-a[i]。
也就是： $a n s = ∣ a_{1} - t ∣ + ∣ a_{2} + a_{1} - 2 t ∣ + ∣ a_{3} + a_{2} + a_{1} - 3 t ∣ + \dots + ∣ \sum_{i = 1}^{n} a_{i} - n t ∣$
如果令 $s_{k} = (\sum_{i = 1}^{k} a_{i}) - k t = \sum_{i = 1}^{k} (a_{i} - t)$
$a n s = \sum_{i = 1}^{n} ∣ s_{i} ∣$
如果 $b_{i} = a_{i} - t$ ，答案就是b的n个前缀和的绝对值之和。

如果是n个人站成一圈，那么，必然有两个人之间是没有交换的，将这两个人断开，变成一条链，假设在位置p和p+1之间断开，且s是原序列的前缀和，则新的前缀和从p+1处开始：
$∣ s_{p + 1} - s_{p} ∣$
$∣ s_{p + 2} - s_{p} ∣$
$\dots$
$∣ s_{n} - s_{p} ∣$
$∣ s_{n} + s_{1} - s_{p} ∣$
$\dots$
$∣ s_{n} + s_{p - 1} - s_{p} ∣$
$∣ s_{n} + s_{p} - s_{p} ∣$
如果s是b的前缀和，则 $s_{n} = 0$
$a n s = \sum_{i = 1}^{n} ∣ s_{i} - s_{p} ∣$ ,欲使ans最小， $s_{p}$ 为s的中位数

有n个人,第i个人站在 $x_{i}$ 的位置，求使他们站成连续的一列的最小花费。
显然，每个人的相对位置不变，设最终他们站在点a、a+1、… a+n-1点，则花费
$a n s = \sum_{i = 1}^{n} ∣ x_{i} - (a + i - 1) ∣ = \sum_{i = 1}^{n} ∣ (x_{i} - i + 1) - a ∣$ ，所以a是序列：
$b_{i} = x_{i} - i - 1$ 的中位数。