均分纸牌问题

· · 算法·理论

本文同步发表于 cnblogs。

普通均分纸牌问题

P1031 [NOIP 2002 提高组] 均分纸牌

这道题是普通的均分纸牌问题。直接贪心即可。设 sum = \sum a_i，avg = \displaystyle \frac{sum}{n}，则很显然，如果 a_i > avg，就把多余的纸牌放到第 i+1 堆，反之亦然。

代码：

#include <bits/stdc++.h>
using namespace std;

const int N = 105;

int n, sum;
int a[N]; 

int main()
{
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
        scanf("%d", &a[i]), sum += a[i];
    sum /= n;
    for (int i = 1; i <= n; i++)
        a[i] -= sum;
    int ans = 0;
    for (int i = 1; i <= n; i++)
    {
        if (a[i] != 0)
        {
            ans++;
            a[i + 1] += a[i];
        }
    }
    printf("%d\n", ans);
    return 0;
}

环形均分纸牌问题

P2512 [HAOI2008] 糖果传递

这道题就是环形均分纸牌问题的板子题。我们假设每一个人都向他的左侧给糖果。设 x_i 代表 i 向 i - 1 传的糖果数量。特别地，x_1 代表 1 向 n 传的糖果数量。如果 x_i < 0，则说明 i 向 i+1 给了 -x_i 颗糖果。那如果要最终每一个人的糖果都相等（即 \forall i \in \{1, 2, \ldots, n\}, a'_i = avg），就会有：

\left\{ \begin{aligned} &a_i - x_i + x_{i+1} = avg \, (1 \le i < n) \\ &a_n - x_n + x_1 = avg \end{aligned} \right.

移项后可得：

\left\{ \begin{aligned} &x_2 = avg + x_1 - a_1 \\ &x_3 = avg + x_2 - a_2 \\ & \dots \\ &x_n = avg + x_{n-1} - a_{n-1} \\ &x_1 = avg + x_n - a_n \end{aligned} \right.

从小到大依次将 x_i 代入 x_{i+1}，即可得：

\begin{aligned} x_i = x_1 - \sum_{j=1}^i a_j + i \times avg \end{aligned}

此时我们设：

\begin{aligned} c_i = \sum_{j=1}^i a_j - i \times avg \end{aligned}

则：

x_i = x_1 - c_i

回到题目，如果要最小化步骤，其实就是使 \sum |x_i| 最小，即使 \sum |x_1 - c_i| 最小。观察其几何意义，就会发现这是一道初中数学题。几何意义就是在数轴上选择一个点 A，使得 A 到 c_{1,2,\dots,n} 的距离和最小。

这就是一道货仓选址问题。

P10452 货仓选址

根据初中学到的知识，就会得出结论：若 n 为偶数，则点 A 选在中间两个点之间一定最优。否则，点 A 为中间的点时一定最优。证明略。

代码：

#include <bits/stdc++.h>
using namespace std;

const int N = 1e5 + 5;

int n;
int a[N];

int main()
{
  scanf("%d", &n);
  for (int i = 1; i <= n; i++)
      scanf("%d", &a[i]);
  sort(a + 1, a + n + 1);
  int ans = 0;
  for (int i = 1; i <= n / 2; i++)
      ans += (a[n - i + 1] - a[i]);
  printf("%d\n", ans);
  return 0;
}

回到糖果传递问题，我们会发现现在就十分简单了。直接上代码：


#include <bits/stdc++.h>
#define int long long
using namespace std;

const int N = 1e6 + 5;

int n, sum; int a[N], c[N];

signed main() { scanf("%lld", &n); for (int i = 1; i <= n; i++) scanf("%lld", &a[i]), sum += a[i]; int avg = sum / n; for (int i = 1; i <= n; i++) c[i] = c[i - 1] - a[i - 1] + avg; sort(c + 1, c + n + 1); int ans = 0; for (int i = 1; i <= n / 2; i++) ans += c[n - i + 1] - c[i]; printf("%lld\n", ans); return 0; }


## 练习题
[**P3051 [USACO12MAR] Haybale Restacking G**](https://www.luogu.com.cn/problem/P3051)

这道题是 P2512 的变形，只需要把原本的 $avg$ 换成每一个 $b_i$ 即可，其他的与上题一样。[代码](https://www.luogu.com.cn/record/233599987)。

[**P10453 七夕祭**](https://www.luogu.com.cn/problem/P10453)

首先发现行和列互不影响，于是就可以对行、列分别进行 P2512 的做法。注意如果当前总数不是 $x$ 的倍数，则这方面无解（$x$ 根据你求的是行还是列断定）。最后判断即可。[代码](https://www.luogu.com.cn/record/233599935)。