本题是一个比较经典的问题（环形均分纸牌问题），我也不知道为什么它在网络流 24 题里面出现。但是作为一道比较典的排序算法的题，还是放出来讲一下。
solution
假设 \(a_1\) 给 \(a_n\) 了 \(x_1\) 张纸牌，\(a_2\) 给 \(a_1\) 了 \(x_2\) 张纸牌......（ \(x_i\) 可正可负）。
因此操作数量为 \(|x_1|+|x_2|+ \cdots |x_n|\)。
令 \(a=\frac{a_1+a_2 + \cdots + a_n}{n}\)。
因此可以列出下面的式子：
\[\left\{\begin{matrix} a_1-x_1+x_2=a \\ a_2-x_2+x_3=a \\ \cdots \\ a_n-x_n+x_1=a \\ \end{matrix}\right. \]将所有式子加起来，会发现是一个恒等式，因此不具有唯一解。
将方程进行等价代换：
\[\left\{\begin{matrix} x_1-x_2=a_1-a \\ x_2-x_3=a_2-a \\ \cdots \\ x_{n-1}-x_n=a_{n-1}-a \\ x_n-x_1=a_n-a \end{matrix}\right. \]令 \(x_1\) 为自由变量，来表示其他变量
\[\left\{\begin{matrix} x_1=x_1-0\\ x_2=x_1-(a_1-a)\\ x_3=x_1-(a_1+a_2-2a)\\ \cdots \\ x_n=x_1-[a_1+a_2+\cdots +a_{n-1}-(n-1)a] \end{matrix}\right. \]后面的一堆 a 都为常数，记为 \(C_i\)
因此看最上面 \(|x_1|+|x_2|+ \cdots |x_n|\) 的式子，就可以转化为 \(|x_1-C_1|+|x_1-C_2|+\cdots + |x_1-C_n|\)
将其看作数轴上的一堆点：
可以将 \(x_1\) 取作中位数能将操作次数最小化
- 证明：
绝对值不等式： \(|a|+|b| \ge |a+b|\)
假设 C 序列已排好序，将上式分组为 \((|x_1-C_1|+ |C_n-x_1|) +(|x_1-C_2|+|C_{n-1}-x_1|) \cdots \ge |C_n - C_1 + C_{n-1} - C_2 + C_{n-2} - C_3 + \cdots + C_{\frac{n+1}{2}} - x_1|\)
因此令 \(x_1\) 取到中位数即可
完整代码：
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e6 + 10;
ll a[N], c[N], avg;
ll n;
int main()
{
scanf("%lld", &n);
avg = 0;
for(int i = 1; i <= n; i ++ )
{
cin >> a[i];
avg += a[i];
}
avg /= n;
c[1] = 0;
for(int i = 2; i <= n; i ++ ) c[i] = c[i - 1] + a[i] - avg;
sort(c + 1, c + n + 1);
ll res = 0;
for(int i = 1; i <= n; i ++ ) res += abs(c[i] - c[(n + 1) / 2]);
cout << res << endl;
return 0;
}
PS：经验
标签：right,matrix,int,题解,ll,cdots,avg,P4016 From： https://www.cnblogs.com/crimsonawa/p/17541998.html