纸牌均分问题

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

有n个人站成一排，每个人有 $a_i$ai​张纸牌，求最小移动次数使得每个人纸牌数一样，一张纸牌交给旁边的人记为一次移动。
如果tot是n的倍数，则有解，设t=tot/n
遍历一遍，对于第i个人，ans+=abs(a[i]-t)，a[i+1]-=t-a[i]。
也就是： $ans=\mid a_1-t\mid +\mid a_2+a_1-2t\mid +\mid a_3+a_2+a_1-3t\mid +\cdots +\mid {\sum }_{i=1}^n{a}_i-nt\mid$ans=∣a1​−t∣+∣a2​+a1​−2t∣+∣a3​+a2​+a1​−3t∣+⋯+∣∑i=1n​ai​−nt∣
如果令 $s_k=\left({\sum }_{i=1}^k{a}_i\right)-kt={\sum }_{i=1}^k(a_i-t)$sk​=(∑i=1k​ai​)−kt=∑i=1k​(ai​−t)
$ans={\sum }_{i=1}^n\mid s_i\mid$ans=∑i=1n​∣si​∣
如果 $b_i=a_i-t$bi​=ai​−t，答案就是b的n个前缀和的绝对值之和。

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

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