自动搬运

查看原文

来自洛谷，原作者为

	big_news away from OI | substandard competitor

搬运于2025-08-24 21:34:17，当前版本为作者最后更新于2019-06-21 11:36:34，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

纸牌均分问题

这种题型大概有两种通解：费用流解法（如网络流24题中的负载平衡问题）和数学解法。但是解法一特别容易被卡MLE，能运行的数据范围大概只有$n\leqslant 100$，所以这题来谈谈数学解法。

分析

假设有五个书架1,2,3,4,5，其中1号向2号搬5本书，2号向1号搬1本书，1号向5号搬3本书，也可以看作1号向5号搬了3本书，2号向1号搬了-4本书。

于是可以得出一个结论，即任意一个书架给别的书架的书本数总可以看作一个定值。假设1号只给5号书，2号只给1号书，......，5号只给4号书，且给的书的数量分别为$x_1,x_2,...,x_5$，那么$x_1,x_2,...,x_5$一定有绝对值最小的确定的值。现在我们要使$\sum\limits_{1\leqslant i\leqslant 5}|x_i|$最小，显然要求出这些“确定的值”。

数学推理

头秃系列开始

设每个书架原先分别有$a_1,a_2,...,a_n$的书。因为每个书架最终的书本数为$\sum\limits_{1\leqslant i\leqslant n}a_i \div n$，设这个数为$\overline a$，则有以下等式：

$$\begin{aligned} a_1 = \overline a - x_2 + x_1 \\ a_2 = \overline a - x_3 + x_2 \\ ... \\ a_5 = \overline a - x_1 + x_5 \end{aligned} $$

移项，得：

$$\begin{aligned} x_2 = x_1 - (a_1-\overline a) \\ x_3 = x_2 - (a_2 - \overline a) \\ ... \\ x_5 = x_1 - (a_5 - \overline a)\end{aligned} $$

将前式分别带入后式可得：

$$\begin{aligned} x_1 = x_1 \\ x_2 = x_1 - (a_1-\overline a) \\ x_3 = x_1 - (a_1 + a_2 - 2\overline a) \\ ... \\ x_5 = x_1 - (a_1+a_2+a_3+a_4 - 4\overline a)\end{aligned} $$

可知：

$$x_n = x_1 - (\sum\limits_{1\leqslant 1< n}a_i - (n-1)\times \overline a) $$

设$c_1 = a_1 - \overline a,c_2 = a_1 + a_2 - 2\overline a,...$，以此类推，可知$x_n = x_1 - c_{n-1}$。同时有递推式$c_i = c_{i-1} + a_i - \overline a$。这个递推式与$x$取值无关，且总有$c_0 = 0$，因此可以计算出所有$c_i$的值。

又有$x_2 = x_1 - c_1,x_3= x_1- c_2,...$，则$\sum\limits_{1\leqslant i\leqslant 5}|x_i|$可表示为：

$$|x_1| + |x_1 -c_1| +|x_1-c_2| + ... +|x_1-c_4|$$

这也可以看作数轴上每个$c_i$到$x_1$的距离之和。那么我们就要找一个$x_1$，使得在数轴上它到每个$c_i$的距离最小。这个$x_1$即是$c_1,c_2,...,c_4$的中位数。

证明

先把$c_1,c_2,...,c_4$排好序，表示在数轴上，如下图所示。

任取一$x_1$，则距离之和可以化为$ \text{dist}(c_1,c_4) + \text{dist}(c_2,c_3) +2\times \text{dist}(c_2,x_1)$。其中$\text{dist}(c_1,c_4) + \text{dist}(c_2,c_3)$为定值，那么让$\text{dist}(c_2,x_1)$最小一定会更优一点。它的最小值为$0$，此时$x_1$选在$c_2$上。

归纳，可知将$x_1$选在$c_1\text{~}c_4$中的一个点上一定要优一点。

然后再分别尝试$c_1,c_2,...,c_4$这些点，不难发现$x_1$选的越靠中间距离之和越小，故可知$x_1$取$c_1,c_2,...,c_4$的中位数。

解决

那么$x_1$就很好求了，然后就可以推出所有的$x$值。第一问就很容易的解决了，第二问只需输出$x_i$和$-x_{i+1}$即可。最后还要再处理一下环。

注意，当$n$为偶数时，两个中位数取哪一个都可以。

代码

#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<algorithm>
using namespace std;

#define LL long long

LL read(){ 
    LL s=0,ne=1; char c=getchar();
    for(;c<'0'||c>'9';c=getchar()) if(c=='-') ne=-1;
    for(;c>='0'&&c<='9';c=getchar()) s=((s<<1)+(s<<3))+c-'0';
    return s*ne;
}

const int CN=1e6+6;

LL n,x1,a[CN],c[CN],_a,rec[CN];
LL llabs(LL a) {return a>0 ? a:-a;}

int main()
{
    n=read();
    LL sigma = 0;
    for(int i=1;i<=n;i++) 
        a[i] = read(),sigma += a[i];
    _a = sigma/n; //求平均值 
    
    rec[0] = c[0] = 0;    
    for(int i=1;i<=n;i++)
        rec[i] = c[i] = c[i-1]+a[i]-_a; //递推c[i]
            
    sort(c+1,c+n+1);
    x1 = c[(n+1)/2]; //计算中位数
        
    LL ans=0;
    for(int i=1;i<=n;i++)
        ans += llabs(x1-c[i]); //求代价
    printf("%lld\n",ans);
    for(int i=1;i<n;i++)
        printf("%lld %lld\n",x1-rec[i-1],-(x1-rec[i])); //输出搬运数
    printf("%lld %lld",x1-rec[n-1],-x1); //处理环
    
    return 0;
}

$$- - - - \mathcal{End} - - - -$$