题目链接

算法竞赛进阶指南-35.糖果传递

有 $n$ 个小朋友坐成一圈，每人有 $a[i]$ 个糖果。

每人只能给左右两人传递糖果。

每人每次传递一个糖果代价为 $1$。

求使所有人获得均等糖果的最小代价。

输入格式

第一行输入一个正整数 $n$，表示小朋友的个数。

接下来 $n$ 行，每行一个整数 $a[i]$，表示第 $i$ 个小朋友初始得到的糖果的颗数。

输出格式

输出一个整数，表示最小代价。

数据范围

$1 \le n \le 1000000$,
$0 \le a[i] \le 2 \times 10^9$,
数据保证一定有解。

输入样例：

4
1
2
5
4

输出样例：

4

Method : 推公式

本题是非常经典的环形均分纸牌问题：

一定存在一个最优解方案，使得环上有相邻的两个人之间没有发生交换，
那么以这两个人中间作为断点，破环成链，此时环形均分纸牌问题可以看作链式均分纸牌问题。

那么如何找到该断点？如果要枚举断点位置，每次做一遍链式均分纸牌，时间复杂度$O(n^2)$，显然不可行。

先来看链式均分纸牌:

假设一共有$N$个人，每个人初始卡牌数量为$c_i$，纸牌总数量为$T$。

第 1 个人为了达到平均持有数, 需要向第 2 个人传递 $c_1-T / N$ 数量的牌 (正数是给, 负数是拿)
第 2 个人为了达到平均持有数, 需要向第 3 个人传递 $c_2-T / N+c_1-T / N$ 数量的牌
…
第n-1个人为了达到平均持有数, 需要向第 $n$ 个人传递 $\sum_{i=1}^{n-1} c_i-(n-1) \times T / N$ 数量的牌
此时前 n-1 人都达到了平均数，则第 n 个人必然也达到了平均数，即最后一个人传递卡牌数量为0​

再回到环形均分卡牌:

设$\left(A_i=\sum_{j=1}^n\left(c_j-\frac{T}{N}\right), S_i=\sum_{j=1}^i A_j\right)$

把n个人的 $A_i$ 和 $S_i$ 罗列出来 ：

$\begin{array}{cc}A_1 & S_1 \\ A_2 & S_2 \\ \cdots & \cdots \\ A_k & S_k \\ A_{k+1} & S_{k+1} \\ \cdots & \cdots \\ A_n & S_n\end{array}$

考虑在第 $k$ 个人之后断开, 则破环成链有:

$\begin{array}{cc} A_{k+1} & S_{k+1}-S_k \\ \cdots & \cdots \\ A_n & S_n-S_k \\ A_1 & S_1+S_n-S_k \\ A_2 & S_2+S_n-S_k \\ \cdots & \cdots \\ A_k & S_k+S_n-S_k \end{array}$

那么链式均分纸牌，其最优解必是最后一个人不需要传递卡牌，即$S_k+S_n-S_k = S_n = 0$。

那么即可以转换为求$\sum_{i=1}^n\left|S_i-S_k\right|$的最小值，即转化为货仓选址问题。

#include <iostream>
#include <algorithm>

using namespace std;

const int N = 1e6 + 7;

typedef long long LL;

int n;
int a[N];
LL s[N];

int main() {
    cin >> n;
    LL sum = 0;
    for (int i = 1; i <= n; i ++) {
        scanf("%d", &a[i]);
        sum += a[i];
    }
    
    LL avg = sum / n;
    for (int i = 1; i <= n; i ++) {
        a[i] -= avg;
    }
    
    for (int i = 1; i <= n; i ++) {
        s[i] += s[i - 1] + a[i];
    }
    sort(s + 1, s + n + 1);

    LL cost = 0;
    for (int i = 1; i <= n / 2; i ++) {
        cost += abs(s[n + 1 - i] - s[i]);
    }
    
    cout << cost << endl;
    
    return 0;
}

复杂度分析

• 时间复杂度${O(n)}$， 其中$n$前缀和的预处理。
• 空间复杂度${O(n)}$，主要是数组$a[N]$和$s[N]$。

补充

均分纸牌

Acwing-1536.均分纸牌

#include <iostream>

using namespace std;

const int N = 100 + 7;

int n;
int a[N];
int s[N];

int main() {
    cin >> n;
    int sum = 0;
    for (int i = 1; i <= n; i ++) {
        scanf("%d", &a[i]);
        sum += a[i];
    }
    
    int avg = sum / n;
    for (int i = 1; i <= n; i ++) {
        a[i] -= avg;
    }
    
    int res = 0;
    int cost = 0;
    for (int i = 1; i <= n; i ++) {
        s[i] = s[i - 1] + a[i];
        if (s[i] != 0) res ++;
        // cost += abs(s[i]);   // 计算每次只能移动一个的移动次数
    }
    
    cout << res << endl;
    
    return 0;
}

参考:

https://aztl.blog.luogu.org/luo-gu-p2512-haoi2008-tang-guo-zhuan-di-ti-xie

https://www.acwing.com/solution/content/41677/