题解 P2125 【图书馆书架上的书】

big_news · 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，则有以下等式：

移项，得：

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

可知：

设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|可表示为：

这也可以看作数轴上每个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;
}