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

逆天四倍经验 原题链接：[糖果传递](https://www.luogu.com.cn/problem/P2512)，[分金币](https://www.luogu.com.cn/problem/P5817)，[P2125 图书馆书架上的书](https://www.luogu.com.cn/problem/P2125)，[P4016 负载平衡问题](https://www.luogu.com.cn/problem/P4016) 狠狠的AC~ 话虽如此，但我仍觉得这是值得一讲的好题 为了方便，接下来我们以“糖果传递”这一题为例 题意翻译应该不用了吧（ 一眼看下去似乎无从下手啊，试着多从几个角度考虑 ### 动态规划： 如果当成线性dp的话，因为有环的出现而不好解决；区间dp角度的话，有点像石子合并那道题，但是不完全一样（完全不一样），而且时间复杂度也完全对不上，过 ### 网络流： 似乎可行，因为每个点的糖果数最后都是要回归平均值的，而用来补充**糖果数小于平均值的点**的糖果一定来自**糖果数大于平均值的点**，此时从大的点运输过来的代价就是两点间的距离，所以对于每个点向它的左右两个点连接一条容量为无限，费用为1的边，从源点向每个点连一条容量为糖果数，费用为0的边，从每个点向汇点连一条容量为平均值，费用为0的边，跑最小费用最大流即可 事实上，这就是[P4016 负载平衡问题](https://www.luogu.com.cn/problem/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 ```cpp #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); } ```