题解 P4016 【负载平衡问题】

· · 题解

这玩意出自“网络流24题”？可是。。。好像是贪心啊。

这题的难点主要是列方程：

首先，给没学《数据的分析（八年级下）》就来切此题的巨佬一点注释：

\overline{x}_a$ 表示平均数，读作x bá，$\overline{x}_a=\dfrac{a_1+a_2+......+a_n}{n} m_{0.5}(a_1,a_2,......,a_n)$ 表示一组数据的中位数。文中取$a_{n/2+1}

设K_1,K_2,......,K_n表示第1,2,......,n个人给他左边的人的货物数。

*SP：K_1表示第一个人给第N个人的货物数，是个未知数。

则有： $A_1-K_1+K_2=\overline{x}_A

故有：

同理可得：

\begin{cases}K_2=\overline{x}_A+K_1-A_1\\K_3=\overline{x}_A+K_2-A_2\\...\\K_n=\overline{x}_A+K_{n-1}-A_n\end{cases}

这是一个n元1次方程，怎么解？

暴力！ 当然是用代入法消元啊

以K_3为例，K_3=2\overline{x}_A+K_1-A_1-A_2

我们设X_i=-i\overline{x}_A+\sum\limits_{j=1}^{i-1}{A_j}

做差，得：

观察这个式子，我们可以发现一个一般规律：

然后：

我们知道：

ans=\sum\limits_{i=1}^{n}{|K_i|}

故：

ans=|K_1-0|+|K_1-X_1|+......+|K_1+X_{n-1}|

∴min \{ans\}=min\{|K_1-0|+|K_1-X_1|+......+|K_1+X_{n-1}|\}

这个式子的几何意义：

在数轴上选择一个K_1，使之到0,X_1,X_2,......,X_{n-1}的距离之和最小

这就是某个“输油管道问题”【橙题】

这个K_1我们要给它赋一个最优值：

这个值就是m_{0.5}\{0,X_1,X_2,......,X_{n-1}\}。

证明略

使用①和②即可解此题。 ```cpp #include<bits/stdc++.h> #define int long long using namespace std; const int maxn=1e6+5; int a[maxn],x[maxn]; int n; inline int get() { int x=0;int f=1;char c=getchar(); while(!isdigit(c)) { if(c=='-') f=-1; c=getchar(); } while(isdigit(c)) { x=x*10+c-'0'; c=getchar(); } return x*f; } signed main() { n=get(); int x_ba=0; for(register int i=1;i<=n;i++) { a[i]=get(); x_ba+=a[i]; } x_ba/=n; for(register int i=1;i<=n;i++) { x[i]=x[i-1]-a[i]+x_ba; } sort(x+1,x+1+n); int m=x[n/2+1],ans=0; for(register int i=1;i<=n;i++) { ans+=abs(x[i]-m); } cout<<ans<<endl; } ```