均分纸牌问题

字数统计: 4.4k字 | 阅读时长: 19分

114

2023-05-05

摘要: 贪心算法经典问题：均分纸牌

【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】
我的网站：潮汐朝夕的生活实验室
我的公众号：算法题刷刷
我的知乎：潮汐朝夕
我的github：FennelDumplings
我的leetcode：FennelDumplings

本文我们来看一下贪心算法的经典问题：均分纸牌问题。该问题在移牌规则上有两个比较常见的变种，一个是允许环形移牌，一个是每次移动牌的数量增加限制。当每次只能移动 1，且可以环形移牌时，问题可以转化为货仓选址问题，通过中位数解决。

最后我们看一道基于均分纸牌的综合问题，经过分析会发现是一个行列两个方向的环形均分纸牌问题，而环形均分纸牌问题进一步可以分解为均分纸牌和货仓选址问题，这个过程涉及到一个正确性证明。这种将原问题经过层层抽象，最终化为已经解决的经典问题，是一种非常重要的思维方式。

均分纸牌问题

1536. 均分纸牌

有N堆纸牌，编号分别为 1,2,…,N。

每堆上有若干张，但纸牌总数必为 N 的倍数。

可以在任一堆上取若干张纸牌，然后移动。

移牌规则为：在编号为 1 的堆上取的纸牌，只能移到编号为 2 的堆上；在编号为 N 的堆上取的纸牌，只能移到编号为 N−1 的堆上；其他堆上取的纸牌，可以移到相邻左边或右边的堆上。

现在要求找出一种移动方法，用最少的移动次数使每堆上纸牌数都一样多。

例如 N=4，4 堆纸牌数分别为：(9,8,17,6)。

移动 3 次可达到目的：

从第三堆取四张牌放入第四堆，各堆纸牌数量变为:(9,8,13,10)。
从第三堆取三张牌放入第二堆，各堆纸牌数量变为:(9,11,10,10)。
从第二堆取一张牌放入第一堆，各堆纸牌数量变为:(10,10,10,10)。

输入格式
第一行包含整数 N。
第二行包含 N 个整数，A1,A2,…,AN 表示各堆的纸牌数量。

输出格式
输出使得所有堆的纸牌数量都相等所需的最少移动次数。

数据范围
1<=N<=100,
1<=Ai<=10000

输入样例：
4
9 8 17 6
输出样例：
3

算法: 贪心

假设共 N 堆纸牌，总牌数为 M N。*经过移动后，N 堆纸牌都是 M 张。

我们从 A[0] 考虑到 A[N-1]。

(1) 首先考虑 A[0]

如果 A[0] = M，那么不用移动，直接考虑 A[1] 即可。
如果 A[0] > M，那么通过 1 次移动将 A[0] - M 移动到 A[1]，然后再考虑 A[1]。
如果 A[0] < M，那么就需要从 A[1] 中移动 M - A[0] 张牌到 A[0]。

上面 3 种情况中，第三种情况比较复杂，需要再根据 A[1] 情况分类讨论。

如果 A[1] >= M - A[0]，直接通过 1 次移动将 M - A[0] 从 A[1] 移到 A[0]，在考虑 A[1] 即可。
如果 A[1] < M - A[0]，那么我们先不执行从 A[1] 到 A[0] 的移动，而先考虑 A[2] 的移动，通过 A[2] 到 A[1] 的移动使得 A[1] 的牌数刚好为 2M - A[0] 即可，此时再将其中的 M - A[0] 移动给 A[0] 即可。此时 A[1] 到 A[0] 依然只花费了 1 次移动。

上面 2 种情况中，第 2 种情况下，当我们考虑 A[2] 移动到 A[1] 时，除了要保证 A[1] 的 M 张牌以外，还要保证 M - A[0] 的额外的牌，记为 extra，总共要移动 2M - A[0]，而如果 A[2] 的牌数小于 2M - A[0] 的话，我们又要暂时搁置而先考虑 A[3] 到 A[2] 的移动了，这样 A[3] 需要移动给 A[2] 的牌数就变为了 extra = M + (2M - A[0] - A[1])。

(2) 然后考虑 A[i]

假设现在推进到了 A[i]，考虑 A[i] 的移动，除了要保证 A[i] 的 M 张牌，还要保证 extra 张额外的提供给 A[0..i-1] 的牌。

如果 A[i] = M + extra，那么不用移动，直接考虑 A[i] 即可。同时 extra 清零。
如果 A[i] > M + extra，通过一次移动将 A[i] - (M + extra) 移动到 A[i + 1]，同时 extra 清零，然后再考虑 A[i + 1]。
如果 A[i] < M + extra，那么通过一次移动从 A[i + 1] 中移动 M + extra - A[i] 给 A[i] 即可。A[i + 1] < M + extra - A[i] 也不要紧，因为总牌数为 N * M，暂时缺少的牌后面一定可以补上。也就是我们知道一定可以通过后续移动使得 A[i + 1] 的值为 M + (M + extra - A[i]) 的。

代码(C++)

#include <iostream>
#include <vector>

using namespace std;

int main()
{
    int N;
    cin >> N;
    vector<int> A(N);
    int sum = 0;
    for(int i = 0; i < N; ++i)
    {
        cin >> A[i];
        sum += A[i];
    }
    int M = sum / N;
    int extra = 0;
    int ans = 0;
    for(int i = 0; i < N - 1; ++i)
    {
        if(A[i] > M + extra)
        {
            ++ans;
            A[i + 1] += A[i] - (M + extra);
            extra = 0;
        }
        else if(A[i] < M + extra)
        {
            ++ans;
            extra += M - A[i];
        }
        else
            extra = 0;
    }
    cout << ans << endl;
}

环形均分纸牌

122. 糖果传递

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

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

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

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

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

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

数据范围
1<=n<=1e6,
0<=a[i]<=2e9,
数据保证一定有解。

输入样例：
4
1
2
5
4
输出样例：
4

算法: 货仓选址

本题同样是求均分纸牌的最少步数，与前一题有两点变化，第一点是每次传递只能传递 1，第二点是可以环形传递。

假设共 N 堆纸牌，总牌数为 T = M * N。经过移动后，N 堆纸牌都是 M 张，也就是 $M = \frac{T}{N}$ 。

不考虑环的均分纸牌：贪心

同样首先考虑第 0 堆牌。

a[0] > M，则 0 号需要给 1 号 a[0] - M 张牌，即 a[1] += a[0] - M。
a[0] < M，则 0 号需要从 1 号拿 M - a[0] 张牌，即 a[1] -= M - a[0]。

然后考虑后续的第 1 ~ N - 1 堆牌。考虑到第 i 堆牌时，牌堆的牌数量为 a[i]，首先可能需要移动 M - a[i - 1] 张牌给第 i - 1 堆，之后可能变为负数，但不用担心，因为还可以从第 i + 1 堆拿牌。

因此达到目标所需的最少步数为：

$\sum\limits_{i=1}\limits^{N}|iM - sums[i]|$

其中 sums[i] 是 a 的前缀和 a[0..i-1]。其含义是前缀 a[0..i-1] 最初有 sums[i] 张牌，最终会有 i * M 张牌，多退少补，会与后面的人发生 abs(i * M - sums[i]) 的交换。

令 A[i] = a[i] - M，也就是最初所有人的牌数都减去 M，于是最终每个人手里是 0 张牌，Sums[i] 为 A 的前缀和 A[0..i-1]：

$Sums[i] = \sum\limits_{j=0}\limits^{i-1}A[j] = \sum\limits_{j=0}\limits^{i-1}(a[j] - M) = sums[i] - iM$

于是：

$\sum\limits_{i=1}\limits^{N}|iM - sums[i]| = \sum\limits_{i=1}\limits^{N}|Sums[i]|$

根据以上公式，首先通过 a 数组和平均值 M，构造 A 数组。然后由 A 构造前缀和 Sums，然后 $\sum\limits_{i=1}\limits^{N}|Sums[i]|$ 即为答案。

环形的处理

当 a[0] 与 a[n - 1] 相连时，可以发现一定存在一种最优解的方案，环上某两个相邻的牌堆之间没有发生纸牌交换。证明见后面。

因此一种朴素的做法是可以枚举这个没有发生交换的位置，把环断开，转化为不考虑环的均分纸牌问题。

不考虑环的均分纸牌问题，就是把第 N - 1 个人和第 0 个人之间把环断开。按照前面堆对 $A$ 和 $Sums$ 的定义，这 N 个人对应的 $A$ 和 $Sums$ 分别为：

$\begin{align} & A[0] & Sums[1] - Sums[n]& \\ & A[1] & Sums[2] - Sums[n]& \\ & \cdots & \cdots & \\ & A[n-1] & Sums[n] - Sums[n]& \\ \end{align}$

由于 $A$ 数组均分之后每个人手里有 0 张牌，因此 $Sums[n] = 0$ 。

如果在第 k 个人与第 k - 1 个人之间断开，则这 N 个人对应的 $A$ 和 $Sums$ 如下：

$\begin{align} & A[k] & Sums[k+1] - Sums[k]& \\ & A[k+1] & Sums[k+2] - Sums[k]& \\ & \cdots & \cdots & \\ & A[n-1] & Sums[n] - Sums[k]& \\ & A[0] & Sums[1] - Sums[k]& \\ & \cdots & \cdots & \\ & A[k-1] & Sums[k] - Sums[k]& \\ \end{align}$

因此从 k 与 k - 1 之间断开，所需的最小的步数为：

$\min\limits_{k}\sum\limits_{i=1}\limits^{N}|Sums[i]-Sums[k]|$

$k$ 取何值时上面的值最小，这正是货仓选址问题。 $\{Sums[i]\}$ 为 N 个商店在数轴上的位置， $Sums[k]$ 是货仓的位置。

货仓选址问题是之前解决过的问题，只需要把 $Sums[1..n]$ 排序，取其中位数作为 $Sums[k]$ 即为最优解。推导过程可以参考文章货仓选址与安排邮筒。

环形处理方式的正确性证明

定义 $X_{i}$ ，表示第 $i$ 堆与第 $i-1$ 堆之间传递了 $X_{i}$ 张牌。其中 $i = 0,1,\cdots,n-1$ ， $X_{0}$ 表示第 0 堆与第 n - 1 堆之间的传递。具体地：

如果 $X_{i} > 0$ ，则表示第 i 堆给第 i - 1 堆 $X_{i}$ 张牌。
如果 $X_{i} < 0$ ，则表示第 i 堆从第 i - 1 堆拿了 $-X_{i}$ 张牌。

总操作次数就是 $\sum\limits_{i=0}^{n-1}|X_{i}|$ ，如果我们能证明 $\sum\limits_{i=0}\limits^{n-1}|X_{i}|$ 取到最小值的各种 $\{X_{0}, X_{1}, \cdots, X_{n-1}\}$ 组合中，存在某个组合中有某个 $X_{i} = 0$ 即可。

由于传递后每一堆的牌数均为 $M$ ，可以得到以下线性方程组：

$a_{0} + X_{1} - X_{0} = M \\ a_{1} + X_{2} - X_{1} = M \\ \cdots \\ a_{n-2} + X_{n-1} - X_{n-2} = M \\ a_{n-1} + X_{0} - X_{n-1} = M \\$

也就是：

$\begin{bmatrix} -1 & 1 & & & & \\ & -1 & 1 & & & \\ & & & \ddots & & \\ & & & & -1 & 1 \\ 1 & & & & & -1 \\ \end{bmatrix} \begin{bmatrix} X_{0} \\ X_{1} \\ \vdots \\ X_{n-1} \end{bmatrix} = M - \begin{bmatrix} a_{0} \\ a_{1} \\ \vdots \\ a_{n-1} \end{bmatrix}$

于是 $X_{1}, \cdots, X_{n-1}$ 可以用 $X_{0}$ 表示：

$\begin{bmatrix} X_{0} \\ X_{1} \\ \vdots \\ X_{n-1} \end{bmatrix} = X_{0} - \begin{bmatrix} 0 & & & & & \\ 1 & 0 & & & & \\ 1 & 1 & 0 & & & \\ \vdots & \vdots & \ddots & \ddots & & \\ 1 & 1 & \cdots & 1 & 0 & \\ 1 & 1 & \cdots & 1 & 1 & 0 \\ \end{bmatrix} \begin{bmatrix} a_{0} \\ a_{1} \\ \vdots \\ a_{n-1} \end{bmatrix} + \begin{bmatrix} 0 \\ 1 \\ \vdots \\ n-1 \end{bmatrix} M$

令 $S_{i} = \sum\limits_{j=0}\limits^{i-1}(a_{j} - M)$ ， $i=1,2,\cdots,n-1$ ， $S_{0} = 0$ ，于是：

$\begin{bmatrix} X_{0} \\ X_{1} \\ X_{2} \\ \vdots \\ X_{n-1} \\ \end{bmatrix} = X_{0} - \begin{bmatrix} S_{0} \\ S_{1} \\ S_{2} \\ \vdots \\ S_{n-1} \\ \end{bmatrix}$

因此总操作次数可以表示为：

$\sum\limits_{i=0}\limits^{n-1}|X_{i}| = \sum\limits_{i=0}\limits^{n-1}|X_{0} - S_{i}|$

由以上公式，我们要做的实际上是求 $X_{0}$ 使得 $\sum\limits_{i=0}\limits^{n-1}|X_{0} - S_{i}|$ 最小。

而这正是一维的货仓选址问题，数轴上有 n 个商店 $\{S_{0}, S_{1}, \cdots, S_{n-1}\}$ ，从数轴上选一个点 $X_{0}$ 建立货仓，使得货仓到各个商店的距离之和最小。

一维货仓选址问题是我们之前解决过的一个问题，答案是取 $X_{0}$ 为 n 个商店位置的中位数，也就是 $\{S_{i}\}$ 经过排序后，如果 $n$ 为奇数，则 $X_{0} = S_{\frac{n}{2}}$ ；如果 $n$ 为偶数，则 $X_{0}\in [S_{\frac{n}{2}-1}, S_{\frac{n}{2}}]$ 。

因此不论 n 为奇数还是偶数， $X_{0}$ 都可以取到 $\{S_{i}\}$ 中的某个值使得 $\sum\limits_{i=0}\limits^{n-1}|X_{0} - S_{i}|$ 最小。因此存在某个 $X_{i} = X_{0} - S_{i} = 0$ ，也就是第 i 个堆和第 i - 1 堆之间没有传递。这就证明了【一定存在一种最优解的方案，环上某两个相邻的牌堆之间没有发生纸牌交换。】。 $\square$

代码 (C++)

#include <iostream>
#include <vector>
#include <algorithm>
#include <numeric>
#include <cmath>

using namespace std;

using ll = long long;

int main()
{
    int n;
    cin >> n;
    vector<ll> a(n);
    for(int i = 0; i < n; ++i)
        cin >> a[i];
    ll M = accumulate(a.begin(), a.end(), (ll)0) / n;

    vector<ll> A(n);
    for(int i = 0; i < n; ++i)
        A[i] = a[i] - M;

    vector<ll> Sums(n + 1);
    for(int i = 1; i <= n; ++i)
        Sums[i] = Sums[i - 1] + A[i - 1];
    sort(Sums.begin() + 1, Sums.end());

    int k = n / 2 + 1; // 从 k 与 k - 1 之间断开
    int median = Sums[k];
    ll ans = 0;
    for(int i = 1; i <= n; ++i)
        ans += abs(Sums[i] - median);
    cout << ans << endl;
}

应用：七夕祭

105. 七夕祭

矩形的祭典会场由 $N$ 排 $M$ 列共计 $NM$ 个摊点组成。

虽然摊点很多，不过我们只对其中的一部分摊点感兴趣。

给定了会场各个摊点的布置之后，我们像通过交换相邻的摊点，其中每一行或每一列的第一个位置和最后一个位置也算作相邻。满足以下两个要求：

(1) 各行中我们感兴趣的摊点数一样多

(2) 各列中我们感兴趣的摊点数一样多

我们想知道两个要求最多能满足多少个。在此前提下，至少需要交换多少次摊点。

输入格式：
第一行包含三个整数 N 和 M 和 T，T 表示 cl 对多少个摊点感兴趣。
接下来 T 行，每行两个整数 x,y，表示 cl 对处在第 x 行第 y 列的摊点感兴趣。

输出格式：
首先输出一个字符串。
如果能满足全部两个要求，输出 both；
如果通过调整只能使得各行中感兴趣的摊点数一样多，输出 row；
如果只能使各列中感兴趣的摊点数一样多，输出 column；
如果均不能满足，输出 impossible。
如果输出的字符串不是 impossible， 接下来输出最小交换次数，与字符串之间用一个空格隔开。

数据范围：
1<=N,M<=100000,
0<=T<=min(N∗M,100000),
1<=x<=N,
1<=y<=M

输入样例：
2 3 4
1 3
2 1
2 2
2 3
输出样例：
row 1

算法：环形均分纸牌

交换左右两个相邻的摊点，只会改变某两列感兴趣的摊点数，不会改变各行感兴趣的摊点数；交换上下两个相邻的摊点，只会改变某两行感兴趣的摊点数，不会改变各列感兴趣的摊点数。

因此我们可以独立地执行按行和按列的交换摊点操作，也就是下面两个：

通过最少次数的左右交换使得每列中的感兴趣摊点数相同。
通过最少次数的上下交换使得每行中的感兴趣摊点数相同。

我们考虑第一个问题的思路，第二个问题完全类似。

首先统计初始情况下，每列的感兴趣的摊点总数 $T$ ，记为 $\{a[i]\}_{i=0}^{M-1}$ 。

若 $T$ 不能被 $M$ 整除，则不能满足要求。

若可以整除，则我们的目标是通过最少的交换次数使得各个列都有 $ave = T / M$ 个感兴趣摊点。这是环形均分纸牌问题，一次交换相当于环形均分纸牌问题中的一次移动牌。

按照环形均分纸牌问题的算法，我们只需要建立数组 $A[i] = a[i] - ave$ ，然后对 $A$ 建立前缀和数组 $Sums[i] = \sum\limits_{j = 0}\limits^{i-1}A[j]$ ， $Sums[i] = 0$ 。将 $Sums[1..M]$ 排序后得到中位数 $median = Sums[M/2 + 1]$ ，然后 $\sum\limits_{i=1}\limits^{M}|Sums[i] - median|$ 即为答案。

代码 (C++)

#include <iostream>
#include <vector>
#include <algorithm>
#include <numeric>
#include <cmath>

using namespace std;

using ll = long long;

ll solve(vector<int>& a)
{
    // 解决 a 上的环形均分纸牌问题，返回最小交换次数，不满足则返回 -1
    int n = a.size();
    ll sum = accumulate(a.begin(), a.end(), (ll)0);
    if(sum % n != 0)
        return -1;
    ll M = sum / n;

    vector<ll> A(n);
    for(int i = 0; i < n; ++i)
        A[i] = a[i] - M;

    vector<ll> Sums(n + 1);
    for(int i = 1; i <= n; ++i)
        Sums[i] = Sums[i - 1] + A[i - 1];
    sort(Sums.begin() + 1, Sums.end());

    int k = n / 2 + 1; // 从 k 与 k - 1 之间断开
    int median = Sums[k];
    ll ans = 0;
    for(int i = 1; i <= n; ++i)
        ans += abs(Sums[i] - median);

    return ans;
}

int main()
{
    int N, M, T;
    cin >> N >> M >> T;
    vector<int> a(N); // N 行感兴趣的个数
    vector<int> b(M); // M 列感兴趣的个数
    for(int i = 0; i < T; ++i)
    {
        int x, y;
        cin >> x >> y;
        a[x - 1]++;
        b[y - 1]++;
    }
    ll row_result = solve(a);
    ll col_result = solve(b);
    if(row_result == -1 && col_result == -1)
        cout << "impossible";
    else if(row_result != -1 && col_result != -1)
        cout << "both " << row_result + col_result;
    else if(row_result != -1)
        cout << "row " << row_result;
    else
        cout << "column " << col_result;
}

潮汐朝夕的生活实验室 \Doge 陪伴一个算法工程师的职业生涯

算法疑难杂症

均分纸牌问题

均分纸牌问题

算法: 贪心

(1) 首先考虑 A[0]

(2) 然后考虑 A[i]

代码(C++)

环形均分纸牌

算法: 货仓选址

不考虑环的均分纸牌：贪心

环形的处理

环形处理方式的正确性证明

代码 (C++)

应用：七夕祭

算法：环形均分纸牌

代码 (C++)

算法疑难杂症

均分纸牌问题

算法: 贪心

(1) 首先考虑 A[0]

(2) 然后考虑 A[i]

代码(C++)

环形均分纸牌

算法: 货仓选址

不考虑环的均分纸牌：贪心

环形的处理

环形处理方式的正确性证明

代码 (C++)

应用： 七夕祭

算法：环形均分纸牌

代码 (C++)

应用：七夕祭