P2512 [HAOI2008] 糖果传递 同 P5817 [CQOI2011] 分金币 同 P2125 图书馆书架上的书 同 P4016 负载平衡问题 题解

· · 题解

逆天四倍经验

原题链接：糖果传递，分金币，P2125 图书馆书架上的书，P4016 负载平衡问题

狠狠的AC~

话虽如此，但我仍觉得这是值得一讲的好题

为了方便，接下来我们以“糖果传递”这一题为例

题意翻译应该不用了吧（

一眼看下去似乎无从下手啊，试着多从几个角度考虑

动态规划：

如果当成线性dp的话，因为有环的出现而不好解决；区间dp角度的话，有点像石子合并那道题，但是不完全一样（完全不一样），而且时间复杂度也完全对不上，过

网络流：

似乎可行，因为每个点的糖果数最后都是要回归平均值的，而用来补充糖果数小于平均值的点的糖果一定来自糖果数大于平均值的点，此时从大的点运输过来的代价就是两点间的距离，所以对于每个点向它的左右两个点连接一条容量为无限，费用为1的边，从源点向每个点连一条容量为糖果数，费用为0的边，从每个点向汇点连一条容量为平均值，费用为0的边，跑最小费用最大流即可

事实上，这就是P4016 负载平衡问题最原本的解法，不然你猜它为什么放在网络流24题里（

嗯，对了，就是有个小问题，时间复杂度:O(nmf).....

怎么办，难道真的只能靠暴力搜索了吗

不急，我们来分析一下题目

对于每个点而言，它的糖果要么来自自己本身，要么来自它的左侧或右侧，左右侧同理，很容易想到作两个数组l_i,r_i，表示向左/右边提供多少个糖果，由于要存储的只是糖果的给拿关系，也可以用负数表示拿走多少个糖果，所以事实上我们只需要存储一个数组 x_i 表示向右边提供/拿取多少个糖果,此时的答案为

\sum_{i=1}^{n}|x_i|

设所有数的平均值为tot，此时很容易得出等式:

a_i+x_{i-i}-x_i=tot x_i=a_i+x_{i-1}-tot

对于i=1而言，有

a_1+x_{n}-x_1=tot

设x_1=y

则有

x_2=a_2+y-tot x_3=a_3+x_2-tot=y+a_3+a_2-2\times tot x_i=y+ \sum_{j=1}^{i}a_j-i \times tot

其中\sum_{j=1}^{i}a_j-i \times tot显然可以用前缀和维护

设c_i=\sum_{j=1}^{i}a_j-i \times tot

则答案就转化成了

ans=\sum_{i=1}^{n}|x_i|=\sum_{i=1}^{n}|y+c_i|

神奇！

此时问题就可以抽象为“在数轴上有n个点，求一个点使得它与这些点的距离的和最小”

可以证明当这个点在这些点的中位数时，答案最优，这里就不证明啦，这就叫做中位数定理

Talk is cheap,show me the code

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int Max=2e5+5;
int num[Max];
int n;
int sum[Max];
int tot=0,ans=0;
signed main()
{
    scanf("%lld",&n);
    for(int i=1;i<=n;i++)
    {
        scanf("%lld",&num[i]);
        tot+=num[i];
    }
    tot/=n;
    for(int i=1;i<=n;i++)
    {
        sum[i]=sum[i-1]+tot-num[i];
    }
    sort(sum+1,sum+1+n);
    for(int i=1;i<=n;i++)
    {
        ans+=abs(sum[(n+1)/2]-sum[i]);
    }
    printf("%lld",ans);
}