问题分析

我们有：

• $n$ 个仓库环形排列
• 每个仓库初始有 $a_i$ 个货物
• 目标：通过相邻搬运使得所有仓库货物数相同
• 要求：最小化搬运量（搬运量 = 搬运的货物总数）

设平均值为： [ \text{avg} = \frac{\sum_{i=1}^n a_i}{n} ] 如果 $\text{avg}$ 不是整数，则问题无解（但题目保证有解）。

数学解法（中位数法）

思路

1. 计算每个仓库的盈余/缺额：$d_i = a_i - \text{avg}$
2. 计算前缀和：$s_i = \sum_{k=1}^i d_k$
3. 对前缀和数组排序，取中位数 $m$
4. 最小搬运量 = $\sum_{i=1}^n |s_i - m|$

原理

• 环形均分问题可以转化为线性均分问题
• 中位数性质保证总距离最小
• 时间复杂度：$O(n \log n)$

网络流解法

建图方法

虽然数学解法更优，但也可以用最小费用流：

1. 源点 $S$ 向 $d_i > 0$ 的仓库连边：

   • 容量 = $d_i$，费用 = $0$

2. $d_i < 0$ 的仓库向汇点 $T$ 连边：

   • 容量 = $-d_i$，费用 = $0$

3. 相邻仓库之间连双向边：

   • 容量 = $+\infty$，费用 = $1$（单位搬运成本）

4. 运行最小费用最大流

原理

• 盈余的仓库作为供应点
• 缺额的仓库作为需求点
• 相邻仓库间可以互相搬运，费用为距离1
• 最小费用流会自动找到最优搬运方案

样例验证

输入：

5
17 9 14 16 4

计算：

• 总量 = $17+9+14+16+4 = 60$
• 平均值 $\text{avg} = 12$
• 盈余/缺额 $d_i$：$[5, -3, 2, 4, -8]$

数学解法： 前缀和 $s_i$（从 $d_1$ 开始）：

• $s_1 = 5$
• $s_2 = 2$
• $s_3 = 4$
• $s_4 = 8$
• $s_5 = 0$

排序：$[0, 2, 4, 5, 8]$，中位数 = $4$

搬运量 = $|0-4| + |2-4| + |4-4| + |5-4| + |8-4| = 4+2+0+1+4 = 11$

输出：11

算法步骤（推荐数学解法）

1. 读入 $n$ 和 $a_1 \dots a_n$
2. 计算平均值 $\text{avg} = \frac{\sum a_i}{n}$
3. 计算 $d_i = a_i - \text{avg}$
4. 计算前缀和 $s_i = \sum_{k=1}^i d_k$
5. 排序 $s$，取中位数 $m$
6. 输出 $\sum |s_i - m|$

复杂度分析

• 数学解法：$O(n \log n)$，最优
• 费用流解法：$O(\text{流算法复杂度})$，较慢但更通用

关键点

1. 环形排列通过前缀和中位数处理
2. 搬运量只关心货物移动的总数量，不关心方向
3. 中位数性质保证最优性

总结

这道题展示了组合优化问题的两种思路：

• 数学方法：利用中位数性质直接求解，高效简洁
• 网络流方法：建模为最小费用流，通用但稍慢

在竞赛中推荐使用数学解法。